Quantum algorithm for minimum dominating set problem with circuit design

Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems.This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs.To expedite the search process,a quantum algorithm employing Grover’s search is proposed.However,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover’s search impossible.Thus,a swap test method is introduced to ascertain the number of iterations required.The oracle,diffusion operators,and swap test are designed with achievable quantum gates.The query complexity is O(1.414^(n))and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.

An Improved Randomized Circle Detection Algorithm Using in Printed Circuit Board Locating Mark

This paper presents an improved Randomized Circle Detection (RCD) algorithm with the characteristic of circularity to detect randomized circle in images with complex background, which is not based on the Hough Transform. The experimental results denote that this algorithm can locate the circular mark of Printed Circuit Board (PCB).

Image boundary extraction based on island model genetic algorithms for integrated circuit defect detection

The integrated circuit chip with high performance has a high sensitivity to the defects in manufacturing environments.When there are defects on a wafer,the defects may lead to the degradation of chip performance.It is necessary to design effective detection approaches for the defects in order to ensure the reliability of wafer.In this paper,a new method based on image boundary extraction is presented for the detection of defects on a wafer.The method uses island model genetic algorithms to perform the segmentation of wafer images,and gets the optimal threshold values.The island model genetic algorithm uses two distinct subpopulations,it is a coarse grain parallel model.The individuals migration can occur between the two subpopulations to share genetic materials.A lot of experimental results show that the defect detection method proposed in this paper can obtain the features of defects effectively.

ROUTE SELECTION IN VIRTUAL CIRCUIT DATA NETWORKS BASED ON GENETIC ALGORITHMS

This paper addresses the problem of selecting a route for every pair of communicating nodes in a virtual circuit data network in order to minimize the average delay encountered by messages. The problem was previously modeled as a network of M/M/1 queues. Agenetic algorithm to solve this problem is presented. Extensive computational results across a variety of networks are reported. These results indicate that the presented solution procedure outperforms the other methods in the literature and is effective for a wide range of traffic loads.

FAULT DIAGNOSIS FOR ANALOG CIRCUITS WITH TOLERANCE—MINIMUM TOLERANCE ESTIMATION ALGORITHM

Based on the influence of circuit element tolerances to the k-fault diagnosis, a method of fault diagnosis is presented which is called minimum tolerance estimation algorithm and has clear physical meaning. Using this’method, an effective estimation of the equivalent fault sources can be obtained with less computing time. It is especially worthwhile to point out that an adaptive sub-optimum algorithm, which comes from the above method, requires even less computing-labor and is particularly suitable to more complicated circuits as well as real-time fault location.

A Quantum Algorithm for Finding a Hamilton Circuit

A quantum algorithm for solving the classical NP-complete problem - the Hamilton circuit is presented. The algorithm employs the quantum SAT and the quantum search algorithms. The algorithm is square-root faster than classical algorithm, and becomes exponentially faster than classical algorithm if nonlinear quantum mechanical computer is used.

A Hybrid GA-SQP Algorithm for Analog Circuits Sizing

This study presents a hybrid algorithm obtained by combining a genetic algorithm (GA) with successive quadratic sequential programming (SQP), namely GA-SQP. GA is the main optimizer, whereas SQP is used to refine the results of GA, further improving the solution quality. The problem formulation is done in the framework named RUNE (fRamework for aUtomated aNalog dEsign), which targets solving nonlinear mono-objective and multi-objective optimization problems for analog circuits design. Two circuits are presented: a transimpedance amplifier (TIA) and an optical driver (Driver), which are both part of an Optical Network-on-Chip (ONoC). Furthermore, convergence characteristics and robustness of the proposed method have been explored through comparison with results obtained with SQP algorithm. The outcome is very encouraging and suggests that the hybrid proposed method is very efficient in solving analog design problems.

Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm

We present a rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm with the exact same time complexity. This means that from a quantum circuit algorithm of L gates we can construct a quantum adiabatic algorithm with time complexity of O（L）. Additionally, our construction shows that one may exponentially speed up some quantum adiabatic algorithms by properly choosing an evolution path.

Fault DiagnosisMethod of Energy Storage Unit of Circuit Breakers Based on EWT-ISSA-BP

Aiming at the problem of energy storage unit failure in the spring operating mechanism of low voltage circuit breakers(LVCBs).A fault diagnosis algorithm based on an improved Sparrow Search Algorithm(ISSA)optimized Backpropagation Neural Network(BPNN)is proposed to improve the operational safety of LVCB.Taking the 1.5kV/4000A/75kA LVCB as an example.According to the current operating characteristics of the energy storage motor,fault characteristics are extracted based on Empirical Wavelet Transform(EWT).Traditional BPNN has problems such as difficulty adjusting network weights and thresholds,being sensitive to initial weights,and quickly falling into local optimal solutions.The Sparrow Search Algorithm(SSA)with self-adjusting weight factors combined with bidirectional mutations is added to optimize the selection of BPNN hyperparameters.The results show that the ISSA-BPNN can accurately and quickly distinguish six conditions of motor voltage reduction:motor voltage increase,motor voltage decrease,energy storage spring stuck,transmission gear stuck,regular state and energy storage spring not locked.It is suitable for fault diagnosis and detection of the energy storage part of LVCB.

基于同源录波数据比对的继电保护采样回路异常检测方法

处于改建阶段的智能变电站采样模式复杂,继电保护装置难以发现采样回路轻微异常,导致回路隐患暴露时间严重滞后。针对上述问题,分析改建时期智能变电站的采样模式和二次设备配置情况,提出基于同源录波数据比对的继电保护采样回路异常检测方法。首先,利用双向编码器表征(bidirectional encoder representations from transformers,BERT)语言模型与余弦相似度算法,实现同源录波数据的通道匹配。然后,利用重采样技术和曼哈顿距离完成波形的采样频率统一与时域对齐。最后,基于动态时间规整(dynamic time warping,DTW)算法提出改进算法,并结合采样点偏移量共同设置采样回路的异常判据。算例分析表明,该方法可以完成录波数据的同源通道匹配,实现波形的一致性对齐,并且相比于传统DTW算法,改进DTW算法对异常状态识别的灵敏性和准确性更高。根据异常判据能够有效检测继电保护采样回路的异常状态,确保了智能变电站的安全可靠运行。

Small-Signal Equivalent Circuit Modeling of a Photodetector Chip

A small-signal equivalent circuit model and the ted. The equivalent lumped circuit, which takes the main extraction techniques for photodetector chips are presen- factors that limit a photodetector＇s RF performance into consideration,is first determined based on the device＇s physical structure. The photodetector＇s S parameters are then on-wafer measured, and the measured raw data are processed with further calibration. A genetic algorithm is used to fit the measured data, thereby allowing us to calculate each parameter value of the model. Experimental resuits show that the modeled parameters are well matched to the measurements in a frequency range from 130MHz to 20GHz, and the proposed method is proved feasible. This model can give an exact description of the photodetector chip＇s high frequency performance,which enables an effective circuit-level prediction for photodetector and optoelectronic integrated circuits.

基于粒子群优化算法的量子卷积神经网络

针对当前量子卷积神经网络模型中参数化量子电路缺乏自适应目标选择策略的问题,提出了一种基于粒子群优化算法自动优化电路的量子卷积神经网络模型。该模型通过将量子电路编码为粒子,并利用粒子群优化算法对电路进行优化,从而搜索出在图像分类任务上表现优异的电路结构。基于Fashion MNIST和MNIST标准数据集的仿真实验表明,该模型具有较强的学习能力和良好的泛化性能,准确率分别可达94.7%和99.05%。相较于现有量子卷积神经网络模型,平均分类精度最高分别提升了4.14%和1.43%。

高密度PCB锡膏喷印的分层路径规划

针对传统算法求解高密度印制电路板锡膏喷印路径规划问题存在收敛速度慢、易陷入局部最优的不足,提出了一种融合密度峰值聚类算法和蚁群算法的分层路径规划方法。利用密度峰值聚类算法处理分布呈矩形或线形的高密度焊盘,将原始问题分解为上层聚类中心与下层小规模子问题集合;蚁群算法求解下层子问题获得子路径集合,求解上层聚类中心得到初始全局路径的重组路线;为避免子路径重组过程中陷入局部最优,利用局部搜索算法对初始全局路径进行二次优化,得到最优全局路径。实验结果表明,该分层路径规划方法降低了全局路径求解的复杂度,提升了算法收敛速度,缩短了加工路径总长度,有效提高了高密度印制电路板锡膏喷印的加工效率。

基于AFSA-eCS混合算法的超磁致伸缩换能器输出特性分析

超磁致伸缩换能器工作性能受到电-磁-机多场耦合的影响,常利用多场模型分析其非线性输出特性,而能否准确获取其多场耦合参数决定了模型的准确性,是换能器设计和优化的关键。鉴于换能器多场模型具有参数多、耦合强、参数辨识难等特点。该文提出基于改进人工鱼群和布谷鸟混合的超磁致伸缩换能器多场模型参数辨识方法。首先,考虑切割棒材涡流效应的影响,建立超磁致伸缩换能器电-磁-机多场耦合的综合电路模型,来实现超磁致伸缩换能器输出行为的模拟;其次,针对模型参数维度多、耦合强的问题,提出了改进的人工鱼群和布谷鸟混合算法(AFSA-eCS),该方法引入精英个体反向学习策略、动态步长和动态发现概率以强化局部精细化搜索能力;最后,基于实验平台验证了综合电路模型和AFSA-eCS的有效性。结果表明:AFSA-eCS相较于单一算法与遗传退火混合算法(GA-SA)收敛快、参数辨识精度高,基于所提算法和模型能够快速有效分析换能器不同工况下的输出特性。

Design and realization of synchronization circuit for GPS software receiver based on FPGA

With research on the carrier phase synchronization and symbol synchronization algorithm of demodulation module, a synchronization circuit system is designed for GPS software receiver based on field programmable gate array （FPGA）, and a series of experiment is done on the hardware platform. The result shows the all-digital synchronization and demodulation of GPS intermediate frequency （IF） signal can be realized and applied in embedded real-time GPS software receiver system. It is verified that the decision-directed joint tracking algorithm of carrier phase and symbol timing for received signals from GPS is reasonable. In addition, the loop works steadily and can be used for receiving GPS signals using synchronous demodulation. The synchronization circuit for GPS software receiver designed based on FPGA has the features of low cost, miniaturization, low power and real-time. Surely, it will become one of the development directions for GPS and even GNSS embedded real-time software receiver.

Efficient thermal analysis method for large scale compound semiconductor integrated circuits based on heterojunction bipolar transistor

In this paper, an efficient thermal analysis method is presented for large scale compound semiconductor integrated circuits based on a heterojunction bipolar transistor with considering the change of thermal conductivity with temperature.The influence caused by the thermal conductivity can be equivalent to the increment of the local temperature surrounding the individual device. The junction temperature for each device can be efficiently calculated by the combination of the semianalytic temperature distribution function and the iteration of local temperature with high accuracy, providing a temperature distribution for a full chip. Applying this method to the InP frequency divider chip and the GaAs analog to digital converter chip, the computational results well agree with the results from the simulator COMSOL and the infrared thermal imager respectively. The proposed method can also be applied to thermal analysis in various kinds of semiconductor integrated circuits.

Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection

The binary decision diagrams （BDDs） can give canonical representation to Boolean functions; they have wide applications in the design and verification of digital systems. A new method based on cultural algorithms for minimizing the size of BDDs is presented in this paper. First of all, the coding of an individual representing a BDDs is given, and the fitness of an individual is defined. The population is built by a set of the individuals. Second, the implementations based on cultural algorithms for the minimization of BDDs, i.e., the designs of belief space and population space, and the designs of acceptance function and influence function, are given in detail. Third, the fault detection approaches using BDDs for digital circuits are studied. A new method for the detection of crosstalk faults by using BDDs is presented. Experimental results on a number of digital circuits show that the BDDs with small number of nodes can be obtained by the method proposed in this paper, and all test vectors of a fault in digital circuits can also be produced.

Combinatorial Optimization Based Analog Circuit Fault Diagnosis with Back Propagation Neural Network

Electronic components' reliability has become the key of the complex system mission execution. Analog circuit is an important part of electronic components. Its fault diagnosis is far more challenging than that of digital circuit. Simulations and applications have shown that the methods based on BP neural network are effective in analog circuit fault diagnosis. Aiming at the tolerance of analog circuit,a combinatorial optimization diagnosis scheme was proposed with back propagation( BP) neural network( BPNN).The main contributions of this scheme included two parts:( 1) the random tolerance samples were added into the nominal training samples to establish new training samples,which were used to train the BP neural network based diagnosis model;( 2) the initial weights of the BP neural network were optimized by genetic algorithm( GA) to avoid local minima,and the BP neural network was tuned with Levenberg-Marquardt algorithm( LMA) in the local solution space to look for the optimum solution or approximate optimal solutions. The experimental results show preliminarily that the scheme substantially improves the whole learning process approximation and generalization ability,and effectively promotes analog circuit fault diagnosis performance based on BPNN.

A spintronic memristive circuit on the optimized RBF-MLP neural network

A radial basis function network(RBF)has excellent generalization ability and approximation accuracy when its parameters are set appropriately.However,when relying only on traditional methods,it is difficult to obtain optimal network parameters and construct a stable model as well.In view of this,a novel radial basis neural network(RBF-MLP)is proposed in this article.By connecting two networks to work cooperatively,the RBF’s parameters can be adjusted adaptively by the structure of the multi-layer perceptron(MLP)to realize the effect of the backpropagation updating error.Furthermore,a genetic algorithm is used to optimize the network’s hidden layer to confirm the optimal neurons(basis function)number automatically.In addition,a memristive circuit model is proposed to realize the neural network’s operation based on the characteristics of spin memristors.It is verified that the network can adaptively construct a network model with outstanding robustness and can stably achieve 98.33%accuracy in the processing of the Modified National Institute of Standards and Technology(MNIST)dataset classification task.The experimental results show that the method has considerable application value.

Improved RBF network application in analog circuit fault isolation

One kind of steepest descent incremental projection learning algorithm for improving the training of radial basis function(RBF)neural network is proposed,which is applied to analog circuit fault isolation.This algorithm simplified the structure of network through optimum output layer coefficient with incremental projection learning(IPL)algorithm,and adjusted the parameters of the neural activation function to control the network scale and improve the network approximation ability.Compared to the traditional algorithm,the improved algorithm has quicker convergence rate and higher isolation precision.Simulation results show that this improved RBF network has much better performance,which can be used in analog circuit fault isolation field.