A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
arXiv:quant-ph/0007071
Abstract
Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. In certain special cases (that are classically easy) we know that the quantum algorithm requires a running time that grows as a polynomial in the number of bits. In this paper we present numerical results on randomly generated instances of an NP-complete problem and of a problem that can be solved classically in polynomial time. We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. For both problems considered, for the set of instances studied, the required running time appears to grow slowly as a function of the number of bits.
15 pages, 8 figures, LaTeX with BoxedEPS macros; email to [email protected]
References in corpus (1)
Cited by in corpus (19)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum machine learning: a classical perspective
- Robustness of adiabatic quantum computation
- A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
- Adiabatic state preparation study of methylene
- Experimental implementation of local adiabatic evolution algorithms by an NMR quantum information processor
- An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
- Approximating Fractional Time Quantum Evolution
- Quantum Adiabatic Algorithm and Large Spin Tunnelling
- The Phase Transition in Exact Cover
- Finding cliques by quantum adiabatic evolution
- Simulations of the adiabatic quantum optimization for the Set Partition Problem
- Quantum Adiabatic Computation and the Travelling Salesman Problem
- Limitations of some simple adiabatic quantum algorithms
- Total suppression of a large spin tunneling barrier in quantum adiabatic computation
- Quantum Adiabatic Evolution for Global Optimization in Big Data
- Annealing Approach to Quantum Tomography
- Multi-step quantum algorithm for solving the 3-bit exact cover problem
- Context Mixing via Ground State Search