Physics – Quantum Physics
Scientific paper
2000-07-19
Physics
Quantum Physics
15 pages, 8 figures, LaTeX with BoxedEPS macros; email to farhi@mit.edu
Scientific paper
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.
Farhi Edward
Goldstone Jeffrey
Gutmann Sam
No associations
LandOfFree
A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-545983