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.

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.

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.

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.

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.

Characterization of Exact One-Query Quantum Algorithms for Partial Boolean Functions

The query model(or black-box model)has attracted much attention from the communities of both classical and quantum computing.Usually,quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart.In the history of quantum algorithms,the Deutsch algorithm and the Deutsch-Jozsa algorithm play a fundamental role and both are exact one-query quantum algorithms.This leads us to con-sider the problem:what functions can be computed by exact one-query quantum algorithms?This problem has been ad-dressed in the literature for total Boolean functions and symmetric partial Boolean functions,but is still open for general partial Boolean functions.Thus,in this paper,we continue to characterize the computational power of exact one-query quantum algorithms for general partial Boolean functions.First,we present several necessary and sufficient conditions for a partial Boolean function to be computed by exact one-query quantum algorithms.Second,inspired by these conditions,we discover some new representative functions that can be computed by exact one-query quantum algorithms but have an essential difference from the already known ones.Specially,it is worth pointing out that before our work,the known func-tions that can be computed by exact one-query quantum algorithms are all symmetric functions and the quantum algo-rithm used is essentially the Deutsch-Jozsa algorithm,whereas the functions discovered in this paper are generally asym-metric and new algorithms to compute these functions are required.Thus,this expands the class of functions that can be computed by exact one-query quantum algorithms.

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.

Effects of T-Factor on Quantum Annealing Algorithms for Integer Factoring Problem

The hardness of the integer factoring problem(IFP)plays a core role in the security of RSA-like cryptosystems that are widely used today.Besides Shor’s quantum algorithm that can solve IFP within polynomial time,quantum annealing algorithms(QAA)also manifest certain advantages in factoring integers.In experimental aspects,the reported integers that were successfully factored by using the D-wave QAA platform are much larger than those being factored by using Shor-like quantum algorithms.In this paper,we report some interesting observations about the effects of QAA for solving IFP.More specifically,we introduce a metric,called T-factor that measures the density of occupied qubits to some extent when conducting IFP tasks by using D-wave.We find that T-factor has obvious effects on annealing times for IFP:The larger of T-factor,the quicker of annealing speed.The explanation of this phenomenon is also given.

Simulation of optimal work extraction for quantum systems with work storage

The capacity to extract work from a quantum heat machine is not only of practical value but also lies at the heart of understanding quantum thermodynamics.In this paper,we investigate optimal work extraction for quantum systems with work storage,where extracting work is completed by a unitary evolution on the composite system.We consider the physical requirement of energy conservation both strictly and on average.For both,we construct their corresponding unitaries and propose variational quantum algorithms for optimal work extraction.We show that maximal work extraction in general can be feasible when energy conservation is satisfied on average.We demonstrate with numeral simulations using a continuous-variable work storage.Our work show an implementation of a variational quantum computing approach for simulating work extraction in quantum systems.

Cavity control as a new quantum algorithms implementation treatment

Based on recent experiments [Nature 449, 438 （2007） and Nature Physics 6, 777 （2010）], a new approach for realizing quantum gates for the design of quantum algorithms was developed. Accordingly, the operation times of such gates while functioning in algorithm applications depend on the number of photons present in their resonant cavities. Multi-qubit algorithms can be realized in systems in which the photon number is increased slightly over the qubit number. In addition, the time required for operation is considerably less than the dephasing and relaxation times of the systems. The contextual use of the photon number as a main control in the realization of any algorithm was demonstrated. The results indicate the possibility of a full integration into the realization of multi-qubit multiphoton states and its application in algorithm designs. Yhrthermore, this approach will lead to a successful implementation of these designs in future experiments.

Accelerating Quantum Computing Readiness: Risk Management and Strategies for Sectors

The potential impact of quantum computing on various industries such as finance, healthcare, cryptography, and transportation is significant;therefore, sectors face challenges in understanding where to start because of the complex nature of this technology. Starting early to explore what is supposed to be done is crucial for providing sectors with the necessary knowledge, tools, and processes to keep pace with rapid advancements in quantum computing. This article emphasizes the importance of consultancy and governance solutions that aid sectors in preparing for the quantum computing revolution. The article begins by discussing the reasons why sectors need to be prepared for quantum computing and emphasizes the importance of proactive preparation. It illustrates this point by providing a real-world example of a partnership. Subsequently, the article mentioned the benefits of quantum computing readiness, including increased competitiveness, improved security, and structured data. In addition, this article discusses the steps that various sectors can take to achieve quantum readiness, considering the potential risks and opportunities in industries. The proposed solutions for achieving quantum computing readiness include establishing a quantum computing office, contracting with major quantum computing companies, and learning from quantum computing organizations. This article provides the detailed advantages and disadvantages of each of these steps and emphasizes the need to carefully evaluate their potential drawbacks to ensure that they align with the sector’s unique needs, goals, and available resources. Finally, this article proposes various solutions and recommendations for sectors to achieve quantum-computing readiness.

Variational quantum algorithms for trace norms and their applications

The trace norm of matrices plays an important role in quantum information and quantum computing. How to quantify it in today’s noisy intermediate scale quantum(NISQ) devices is a crucial task for information processing. In this paper, we present three variational quantum algorithms on NISQ devices to estimate the trace norms corresponding to different situations.Compared with the previous methods, our means greatly reduce the requirement for quantum resources. Numerical experiments are provided to illustrate the effectiveness of our algorithms.

Quantum adiabatic algorithms using unitary interpolation

We present two efficient quantum adiabatic algorithms for Bernstein–Vazirani problem and Simon’s problem.We show that the time complexities of the algorithms for Bernstein–Vazirani problem and Simon’s problem are O(1)and O(n),respectively,which are the same complexities as the corresponding algorithms in quantum circuit model.In these two algorithms,the adiabatic Hamiltonians are realized by unitary interpolation instead of standard linear interpolation.Comparing with the adiabatic algorithms using linear interpolation,the energy gaps of our algorithms keep constant.Therefore,the complexities are much easier to analyze using this method.

Variational quantum simulation of thermal statistical states on a superconducting quantum processer

Quantum computers promise to solve finite-temperature properties of quantum many-body systems,which is generally challenging for classical computers due to high computational complexities.Here,we report experimental preparations of Gibbs states and excited states of Heisenberg X X and X X Z models by using a 5-qubit programmable superconducting processor.In the experiments,we apply a hybrid quantum–classical algorithm to generate finite temperature states with classical probability models and variational quantum circuits.We reveal that the Hamiltonians can be fully diagonalized with optimized quantum circuits,which enable us to prepare excited states at arbitrary energy density.We demonstrate that the approach has a self-verifying feature and can estimate fundamental thermal observables with a small statistical error.Based on numerical results,we further show that the time complexity of our approach scales polynomially in the number of qubits,revealing its potential in solving large-scale problems.

Variational quantum simulation of the quantum critical regime

The quantum critical regime marks a zone in the phase diagram where quantum fluctuation around the critical point plays a significant role at finite temperatures.While it is of great physical interest,simulation of the quantum critical regime can be difficult on a classical computer due to its intrinsic complexity.Herein,we propose a variational approach,which minimizes the variational free energy,to simulate and locate the quantum critical regime on a quantum computer.The variational quantum algorithm adopts an ansatz by performing an unitary operator on a product of a single-qubit mixed state,in which the entropy can be analytically obtained from the initial state,and thus the free energy can be accessed conveniently.With numeral simulation,using the one-dimensional Kitaev model as a demonstration we show that the quantum critical regime can be identified by accurately evaluating the temperature crossover line.Moreover,the dependencies of both the correlation length and the phase coherence time with temperature are evaluated for the thermal states.Our work suggests a practical way as well as a first step for investigating quantum critical systems at finite temperatures on quantum devices with few qubits.

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.

Variational quantum semi-supervised classifier based on label propagation

Label propagation is an essential semi-supervised learning method based on graphs,which has a broad spectrum of applications in pattern recognition and data mining.This paper proposes a quantum semi-supervised classifier based on label propagation.Considering the difficulty of graph construction,we develop a variational quantum label propagation(VQLP)method.In this method,a locally parameterized quantum circuit is created to reduce the parameters required in the optimization.Furthermore,we design a quantum semi-supervised binary classifier based on hybrid Bell and Z bases measurement,which has a shallower circuit depth and is more suitable for implementation on near-term quantum devices.We demonstrate the performance of the quantum semi-supervised classifier on the Iris data set,and the simulation results show that the quantum semi-supervised classifier has higher classification accuracy than the swap test classifier.This work opens a new path to quantum machine learning based on graphs.

General Method of Combining Grover and Simon for Attacking Block Ciphers

The compatibility of different quantum algorithms should be considered when these algorithms are combined.In this paper,the method of combining Grover and Simon is studied for the first time,under some preconditions or assumptions.First,we give two preconditions of applying Grover’s algorithm,which ensure that the success probability of finding the marked element is close to 1.Then,based on these two preconditions,it is found out that the success probability of the quantum algorithm for FXconstruction is far less than 1.Furthermore,we give the design method of the Oracle function,and then present the general method of combining Grover and Simon algorithm for attacking block ciphers,with success probability close to 1.

Multipath Selection Algorithm Based on Dynamic Flow Prediction

Traditional traffic management techniques appear to be incompetent in complex data center networks, so proposes a load balancing strategy based on Long Short-Term Memory (LSTM) and quantum annealing by Software Defined Network (SDN) to dynamically predict the traffic and comprehensively consider the current and predicted load of the network in order to select the optimal forwarding path and balance the network load. Experiments have demonstrated that the algorithm achieves significant improvement in both system throughput and average packet loss rate for the purpose of improving network quality of service.