The Quantum Adiabatic Algorithm (QAA) has been proposed as a mechanism for efficiently solving optimization problems on a quantum computer. Since adiabatic computation is analog in nature and does not require the design and use of quantum gates, it can be thought of as a simpler and perhaps more profound method for performing quantum computations that might also be easier to implement experimentally. While these features have generated substantial research in QAA, to date there is still a lack of solid evidence that the algorithm can outperform classical optimization algorithms.
The Quantum Adiabatic Algorithm (QAA) has been proposed as a mechanism for efficiently solving optimization problems on a quantum computer. Since adiabatic computation is analog in nature and does not require the design and use of quantum gates, it can be thought of as a simpler and perhaps more profound method for performing quantum computations that might also be easier to implement experimentally. While these features have generated substantial research in QAA, to date there is still a lack of solid evidence that the algorithm can outperform classical optimization algorithms.
Quantum annealers promise to solve practical optimization problems potentially faster than conventional classical computers. One of the major ongoing debates in this context pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers do not necessarily perform better than classical heuristic solvers. Here, we numerically study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems and a spin glass problem by studying the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we briefly discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.
In this paper, we study two aspects of quantum adiabatic evolution for a prototypical search problem: the optimality of the corresponding algorithm and its relation to the quantum circuit model. Firstly, we propose a general framework for proving the square-root speedup of the quantum adiabatic algorithm to be optimal over classical computation, which is readily applicable to the case of multiple targets. Through this framework, we also find that it is possible to further reduce the time complexity by increasing the physical energy of the system, encompassing results from previous works. Secondly, we find that, on the one hand, when the quantum adiabatic algorithm that achieves quadratic speedup is implemented on a quantum circuit, the time slice needed is always consistent with its time complexity, which also encompasses previous results; on the other hand, however, if a further algorithmic improvement is considered, the time slice always remains invariant. This phenomenon represents a significant observation with potential applications. We anticipate that the main results of this paper will interest the quantum adiabatic computation community and may help us to design efficient quantum algorithms for practical problems in the future.
The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.
Adiabatic quantum optimization is a procedure to solve a vast class of optimization problems by slowly changing the Hamiltonian of a quantum system. The evolution time necessary for the algorithm to be successful scales inversely with the minimum energy gap encountered during the dynamics. Unfortunately, the direct calculation of the gap is strongly limited by the exponential growth in the dimensionality of the Hilbert space associated to the quantum system. Although many special-purpose methods have been devised to reduce the effective dimensionality, they are strongly limited to particular classes of problems with evident symmetries. Moreover, little is known about the computational power of adiabatic quantum optimizers in real-world conditions. Here we propose and implement a general purposes reduction method that does not rely on any explicit symmetry and which requires, under certain general conditions, only a polynomial amount of classical resources. Thanks to this method, we are able to analyze the performance of ``nonideal'' quantum adiabatic optimizers to solve the well-known Grover problem, namely the search of target entries in an unsorted database, in the presence of discrete local defects. In this case, we show that adiabatic quantum optimization, even if affected by random noise, is still potentially faster than any classical algorithm.
The Quantum Approximate Optimization Algorithm (QAOA) is designed to run on a gate model quantum computer and has shallow depth. It takes as input a combinatorial optimization problem and outputs a string that satisfies a high fraction of the maximum number of clauses that can be satisfied. For certain problems the lowest depth version of the QAOA has provable performance guarantees although there exist classical algorithms that have better guarantees. Here we argue that beyond its possible computational value the QAOA can exhibit a form of Quantum Supremacy in that, based on reasonable complexity theoretic assumptions, the output distribution of even the lowest depth version cannot be efficiently simulated on any classical device. We contrast this with the case of sampling from the output of a quantum computer running the Quantum Adiabatic Algorithm (QADI) with the restriction that the Hamiltonian that governs the evolution is gapped and stoquastic. Here we show that there is an oracle that would allow sampling from the QADI but even with this oracle, if one could efficiently classically sample from the output of the QAOA, the Polynomial Hierarchy would collapse. This suggests that the QAOA is an excellent candidate to run on near term quantum computers not only because it may be of use for optimization but also because of its potential as a route to establishing quantum supremacy.
The simple act of slowly varying the parameters of a quantum system so that it remains always in its ground state is extremely rich from an information processing point of view. For an ideal, closed system, this adiabatic evolution is equivalent to full quantum computation, and it is convenient for establishing quantum algorithms for optimization. This review presents adiabatic quantum algorithms, proves the closed-system equivalence of the adiabatic and circuit models of quantum computation, reviews the placement of adiabatic quantum computation in the more general classification of computational complexity theory, and discusses the case of ``stoquastic'' quantum evolutions.