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.

A quantum algorithm for Toeplitz matrix-vector multiplication

Toeplitz matrix-vector multiplication is widely used in various fields,including optimal control,systolic finite field multipliers,multidimensional convolution,etc.In this paper,we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O(κpolylogn),whereκand 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix,respectively.For the case with an unknown generating function,we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L_(1)-normρof the displacement of the structured matrices.Due to the good use of the special properties of Toeplitz matrices,the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.

Quantum Algorithm for Mining Frequent Patterns for Association Rule Mining

Maximum frequent pattern generation from a large database of transactions and items for association rule mining is an important research topic in data mining. Association rule mining aims to discover interesting correlations, frequent patterns, associations, or causal structures between items hidden in a large database. By exploiting quantum computing, we propose an efficient quantum search algorithm design to discover the maximum frequent patterns. We modified Grover’s search algorithm so that a subspace of arbitrary symmetric states is used instead of the whole search space. We presented a novel quantum oracle design that employs a quantum counter to count the maximum frequent items and a quantum comparator to check with a minimum support threshold. The proposed derived algorithm increases the rate of the correct solutions since the search is only in a subspace. Furthermore, our algorithm significantly scales and optimizes the required number of qubits in design, which directly reflected positively on the performance. Our proposed design can accommodate more transactions and items and still have a good performance with a small number of qubits.

Quantum Algorithms for Some Well—Known NP Problems

It is known that quantum computer is more powerful than classical computer.In this paper we present quantum algorithms for some famous NP problems in graph theory and combination theory,these quantum algorithms are at least quadratically faster than the classical ones.

A Note on Shor’s Quantum Algorithm

Shor proposed a polynomial time algorithm for computing the order of one element in a multiplicative group using a quantum computer. Based on Miller’s randomization, he then gave a factorization algorithm. But the algorithm has two shortcomings, the order must be even and the output might be a trivial factor. Actually, these drawbacks can be overcome if the number is an RSA modulus. Applying the special structure of the RSA modulus, an algorithm is presented to overcome the two shortcomings. The new algorithm improves Shor’s algorithm for factoring RSA modulus. The cost of the factorization algorithm almost depends on the calculation of the order of 2 in the multiplication group.

Application of quantum algorithms to direct measurement of concurrence of a two-qubit pure state

This paper proposes a method to measure directly the concurrence of an arbitrary two-qubit pure state based on a generalized Grover quantum iteration algorithm and a phase estimation algorithm. The concurrence can be calculated by applying quantum algorithms to two available copies of the bipartite system, and a final measurement on the auxiliary working qubits gives a better estimation of the concurrence. This method opens new prospects of entanglement measure by the application of quantum algorithms. The implementation of the protocol would be an important step toward quantum information processing and more complex entanglement measure of the finite-dimensional quantum system with an arbitrary number of qubits.

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.

Quantum Algorithms and Experiment Implementations Based on IBM Q

With the rapid development of quantum theory and technology in recent years,especially the emergence of some quantum cloud computing platforms,more and more researchers are not satisfied with the theoretical derivation and simulation verification of quantum computation(especially quantum algorithms),experimental verification on real quantum devices has become a new trend.In this paper,three representative quantum algorithms,namely Deutsch-Jozsa,Grover,and Shor algorithms,are briefly depicted,and then their implementation circuits are presented,respectively.We program these circuits on python with QISKit to connect the remote real quantum devices(i.e.,ibmqx4,ibmqx5)on IBM Q to verify these algorithms.The experimental results not only show the feasibility of these algorithms,but also serve to evaluate the functionality of these devices.

Quantum algorithm for neighborhood preserving embedding

Neighborhood preserving embedding(NPE)is an important linear dimensionality reduction technique that aims at preserving the local manifold structure.NPE contains three steps,i.e.,finding the nearest neighbors of each data point,constructing the weight matrix,and obtaining the transformation matrix.Liang et al.proposed a variational quantum algorithm(VQA)for NPE[Phys.Rev.A 101032323(2020)].The algorithm consists of three quantum sub-algorithms,corresponding to the three steps of NPE,and was expected to have an exponential speedup on the dimensionality n.However,the algorithm has two disadvantages:(i)It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one.(ii)Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA.In this paper,we propose a complete quantum algorithm for NPE,in which we redesign the three sub-algorithms and give a rigorous complexity analysis.It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm,and achieve a significant speedup compared to Liang et al.’s algorithm even without considering the complexity of the VQA.

A Quantum Algorithm for Evaluating the Hamming Distance

We present a novel quantum algorithm to evaluate the hamming distance between two unknown oracles via measuring the degree of entanglement between two ancillary qubits.In particular,we use the power of the entanglement degree based quantum computing model that preserves at most the locality of interactions within the quantum model structure.This model uses one of two techniques to retrieve the solution of a quantum computing problem at hand.In the first technique,the solution of the problem is obtained based on whether there is an entanglement between the two ancillary qubits or not.In the second,the solution of the quantum computing problem is obtained as a function in the concurrence value,and the number of states that can be generated from the Boolean variables.The proposed algorithm receives two oracles,each oracle represents an unknown Boolean function,then it measures the hamming distance between these two oracles.The hamming distance is evaluated based on the second technique.It is shown that the proposed algorithm provides exponential speedup compared with the classical counterpart for Boolean functions that have large numbers of Boolean variables.The proposed algorithm is explained via a case study.Finally,employing recently developed experimental techniques,the proposed algorithm has been verified using IBM’s quantum computer simulator.

Quantum Algorithm for Appointment Scheduling

Suppose a practical scene that when two or more parties want to schedule anappointment, they need to share their calendars with each other in order to make itpossible. According to the present result the whole communication cost to solve thisproblem should be their calendars’ length by using a classical algorithm. In this work, weinvestigate the appointment schedule issue made by N users and try to accomplish it inquantum information case. Our study shows that the total communication cost will bequadratic times smaller than the conventional case if we apply a quantum algorithm in theappointment-scheduling problem.

Quantum Algorithm of Imperfect KB Self-organization. Pt II: Robotic Control with Remote Knowledge Base Exchange

The technology of knowledge base remote design of the smart fuzzy con­trollers with the application of the"Soft/quantum computing optimizer"toolkit software developed.The possibility of the transmission and commu­nication the knowledge base using remote connection to the control object considered.Transmission and communication of the fuzzy controller’s knowledge bases implemented through the remote connection with the control object in the online mode apply the Bluetooth or WiFi technologies.Remote transmission of knowledge bases allows designing many different built-in intelligent controllers to implement a variety of control strategies under conditions of uncertainty and risk.As examples,two different models of robots described(mobile manipulator and(“cart-pole”system)inverted pendulum).A comparison of the control quality between fuzzy controllers and quantum fuzzy controller in various control modes is presented.The ability to connect and work with a physical model of control object without using than mathematical model demonstrated.The implemented technol­ogy of knowledge base design sharing in a swarm of intelligent robots with quantum controllers.It allows to achieve the goal of control and to gain additional knowledge by creating a new quantum hidden information source based on the synergetic effect of combining knowledge.Develop­ment and implementation of intelligent robust controller’s prototype for the intelligent quantum control system of mega-science project NICA(at the first stage for the cooling system of superconducted magnets)is discussed.The results of the experiments demonstrate the possibility of the ensured achievement of the control goal of a group of robots using soft/quantum computing technologies in the design of knowledge bases of smart fuzzy controllers in quantum intelligent control systems.The developed software toolkit allows to design and setup complex ill-defined and weakly formal­ized technical systems on line.

A Parallel Quantum Algorithm for the Satisfiability Problem

In this paper we present a classical parallel quantum algorithm for the satisfiability problem. We have exploited the classical parallelism of quantum algorithms developed in [G.L. Long and L. Xiao, Phys. Rev. A 69 （2004） 052303], so that additional acceleration can be gained by using classical parallelism. The quantum algorithm first estimates the number of solutions using the quantum counting algorithm, and then by using the quantum searching algorithm, the explicit solutions are found.

Quantum Algorithm of Imperfect KB Self-organization Pt I: Smart Control-Information-Thermodynamic Bounds

The quantum self-organization algorithm model of wise knowledge base design for intelligent fuzzy controllers with required robust level considered.Background of the model is a new model of quantum inference based on quantum genetic algorithm.Quantum genetic algorithm applied on line for the quantum correlation’s type searching between unknown solutions in quantum superposition of imperfect knowledge bases of intelligent controllers designed on soft computing.Disturbance conditions of analytical information-thermodynamic trade-off interrelations between main control quality measures(as new design laws)discussed in Part I.The smart control design with guaranteed achievement of these trade-off interrelations is main goal for quantum self-organization algorithm of imperfect KB.Sophisticated synergetic quantum information effect in Part I(autonomous robot in unpredicted control situations)and II(swarm robots with imperfect KB exchanging between“master-slaves”)introduced:a new robust smart controller on line designed from responses on unpredicted control situations of any imperfect KB applying quantum hidden information extracted from quantum correlation.Within the toolkit of classical intelligent control,the achievement of the similar synergetic information effect is impossible.Benchmarks of intelligent cognitive robotic control applications considered.

Quantum algorithm for a set of quantum 2SAT problems

We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability(Q2SAT)problem,which is a generalization of 2-satisfiability(2SAT)problem.For a Q2SAT problem,we construct the Hamiltonian which is similar to that of a Heisenberg chain.All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states.The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace.Our numerical results suggest that the time complexity of our algorithm is O(n^(3.9))for yielding non-trivial solutions for problems with the number of clauses m=dn(n-1)/2(d■0.1).We discuss the advantages of our algorithm over the known quantum and classical algorithms.

Variational quantum algorithms for scanning the complex spectrum of non-Hermitian systems

Solving non-Hermitian quantum many-body systems on a quantum computer by minimizing the variational energy is challenging as the energy can be complex.Here,we propose a variational quantum algorithm for solving the non-Hermitian Hamiltonian by minimizing a type of energy variance,where zero variance can naturally determine the eigenvalues and the associated left and right eigenstates.Moreover,the energy is set as a parameter in the cost function and can be tuned to scan the whole spectrum efficiently by using a two-step optimization scheme.Through numerical simulations,we demonstrate the algorithm for preparing the left and right eigenstates,verifying the biorthogonal relations,as well as evaluating the observables.We also investigate the impact of quantum noise on our algorithm and show that its performance can be largely improved using error mitigation techniques.Therefore,our work suggests an avenue for solving non-Hermitian quantum many-body systems with variational quantum algorithms on near-term noisy quantum computers.

Quantum algorithms for matrix operations and linear systems of equations

Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations.Using the‘sender-receiver’model,we propose quantum algorithms for matrix operations such as matrix-vector product,matrix-matrix product,the sum of two matrices,and the calculation of determinant and inverse matrix.We encode the matrix entries into the probability amplitudes of the pure initial states of senders.After applying proper unitary transformation to the complete quantum system,the desired result can be found in certain blocks of the receiver’s density matrix.These quantum protocols can be used as subroutines in other quantum schemes.Furthermore,we present an alternative quantum algorithm for solving linear systems of equations.

Variational quantum algorithm for node embedding

Quantum machine learning has made remarkable progress in many important tasks.However,the gate complexity of the initial state preparation is seldom considered in lots of quantum machine learning algorithms,making them non-end-to-end.Herein,we propose a quantum algorithm for the node embedding problem that maps a node graph's topological structure to embedding vectors.The resulting quantum embedding state can be used as an input for other quantum machine learning algorithms.With O(log(N))qubits to store the information of N nodes,our algorithm will not lose quantum advantage for the subsequent quantum information processing.Moreover,owing to the use of a parameterized quantum circuit with O(poly(log(N)))depth,the resulting state can serve as an efficient quantum database.In addition,we explored the measurement complexity of the quantum node embedding algorithm,which is the main issue in training parameters,and extended the algorithm to capture high-order neighborhood information between nodes.Finally,we experimentally demonstrated our algorithm on an nuclear magnetic resonance quantum processor to solve a graph model.

Development of a Post Quantum Encryption Key Generation Algorithm Using Electromagnetic Wave Propagation Theory

In today’s rapid widespread of digital technologies into all live aspects to enhance efficiency and productivity on the one hand and on the other hand ensure customer engagement, personal data counterfeiting has become a major concern for businesses and end-users. One solution to ensure data security is encryption, where keys are central. There is therefore a need to find robusts key generation implementation that is effective, inexpensive and non-invasive for protecting and preventing data counterfeiting. In this paper, we use the theory of electromagnetic wave propagation to generate encryption keys.

Near-term quantum computing techniques: Variational quantum algorithms, error mitigation, circuit compilation, benchmarking and classical simulation

Quantum computing is a game-changing technology for global academia,research centers and industries including computational science,mathematics,finance,pharmaceutical,materials science,chemistry and cryptography.Although it has seen a major boost in the last decade,we are still a long way from reaching the maturity of a full-fledged quantum computer.That said,we will be in the noisy-intermediate scale quantum(NISQ)era for a long time,working on dozens or even thousands of qubits quantum computing systems.An outstanding challenge,then,is to come up with an application that can reliably carry out a nontrivial task of interest on the near-term quantum devices with non-negligible quantum noise.To address this challenge,several near-term quantum computing techniques,including variational quantum algorithms,error mitigation,quantum circuit compilation and benchmarking protocols,have been proposed to characterize and mitigate errors,and to implement algorithms with a certain resistance to noise,so as to enhance the capabilities of near-term quantum devices and explore the boundaries of their ability to realize useful applications.Besides,the development of near-term quantum devices is inseparable from the efficient classical sim-ulation,which plays a vital role in quantum algorithm design and verification,error-tolerant verification and other applications.This review will provide a thorough introduction of these near-term quantum computing techniques,report on their progress,and finally discuss the future prospect of these techniques,which we hope will motivate researchers to undertake additional studies in this field.