A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
<|reference_start|>A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability: 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.<|reference_end|>
@article{farhi2000a,
    title={A Numerical Study of the Performance of a Quantum Adiabatic Evolution
  Algorithm for Satisfiability},
    author={Edward Farhi, Jeffrey Goldstone, Sam Gutmann},
    journal={arXiv preprint arXiv:quant-ph/0007071},
    year={2000},
    number={MIT-CTP # 3006},
    archivePrefix={arXiv},
    eprint={quant-ph/0007071},
    primaryClass={quant-ph cs.CC}
}