RECORD
A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
Quantum Physics · Submitted 19 Jul 2000
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Quantum computation by adiabatic evolution, as described in quant-ph/0001106, will solve satisfiability problems if the running time is long enough. | background 1.00 | 0.06 | 0.12 | asserted 0.91 |
| s1 | 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. | background 1.00 | 0.11 | 0.06 | asserted 1.00 |
| s2 | 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. | contribution 0.98 | 0.91 | 0.05 | asserted 0.97 |
| s3 | We simulate a quantum computer (of up to 16 qubits) by integrating the Schrodinger equation on a conventional computer. | method 1.00 | 0.96 | 0.03 | asserted 1.00 |
| s4 | 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. | result 0.99 | 0.95 | 0.82 | hedged possibility 0.95 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
References
How the literature uses it
10 arXiv papers cite this in 11 sentences
Papers citing it · 4 sentences without a confident label
Uses its method or tool 1 paper
-
Let us consider an application of $Ĥ_eff$ to the quantum annealing computation [ref] with a driving Hamiltonian $V̂$ on $ℋ_Λ⊗ℋ_Ω$, introducing a time dependent Hamiltonian such as [equation] with initial condition [equation] that is chosen to be the ground state of $V̂$.
Context Mixing via Ground State Search · Mapping to Ground State Search · 0.84
Compares with it 1 paper
-
Notice that the Hamiltonian of example (a) (or example (b) as the doubled version of example (a)) corresponds to the database searching problem and that the above suggestion might imply an exponential improvement of the well known results by Grover's algorithm [ref] or by the ordinary quantum annealing approach [ref] .
Annealing Dynamics via Quantum Interference of Forward and Backward Time Evolved States · Remarks on the Improved Network · 0.97
Cites it as background 5 papers
-
The adiabatic algorithm [ref] works by initializing a system as an easy-to-prepare ground state of a known Hamiltonian, and then slowly (adiabatically) deforming that system Hamiltonian into the Hamiltonian whose ground state we wish to prepare.
Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization · Background on the adiabatic algorithm · 1.00
-
A beautiful quantum extension of annealing computation – so-called quantum annealing computation – has been proposed [ref] , and is paid lots of attentions today even from industries.
Annealing Dynamics via Quantum Interference of Forward and Backward Time Evolved States · Introduction · 0.99
-
Solving a problem in quantum computation can be transformed to finding the ground state of a problem Hamiltonian that encodes the solution to the problem, e.g. adiabatic quantum computing (AQC) [ref] .
Polynomial-time quantum algorithm for solving the hidden subgroup problem · Introduction · 0.87
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.