Quantum Computation by Adiabatic Evolution

Quantum Computation by Adiabatic Evolution

28 Jan 2000 | Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser
This paper presents a quantum algorithm for solving instances of the satisfiability problem using adiabatic evolution. The algorithm involves a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. The evolution time must be sufficiently long to ensure the system evolves to the desired final ground state. The algorithm is shown to run in polynomial time for certain symmetric cases of the satisfiability problem. The algorithm is based on the principle of quantum adiabatic evolution, which ensures that the system remains in the ground state of the slowly varying Hamiltonian. The key challenge is estimating the minimum energy gap between the ground state and the first excited state of the interpolating Hamiltonian. This gap determines the required evolution time, which must be polynomial in the number of bits for the algorithm to be efficient. The paper discusses several examples, including a three-qubit example where the algorithm successfully finds the unique satisfying assignment of overlapping clauses. It also analyzes the Grover problem, which has a unique satisfying assignment and requires exponential time for the quantum adiabatic evolution, matching the performance of classical algorithms. The paper concludes that while the quantum adiabatic evolution can solve certain problems efficiently, the size of the minimum energy gap determines the algorithm's efficiency. For problems with a large gap, the algorithm runs in polynomial time, while for problems with a small gap, the required evolution time becomes impractically long. The paper also highlights that the structure of the problem plays a crucial role in determining the minimum gap and the efficiency of the algorithm.This paper presents a quantum algorithm for solving instances of the satisfiability problem using adiabatic evolution. The algorithm involves a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. The evolution time must be sufficiently long to ensure the system evolves to the desired final ground state. The algorithm is shown to run in polynomial time for certain symmetric cases of the satisfiability problem. The algorithm is based on the principle of quantum adiabatic evolution, which ensures that the system remains in the ground state of the slowly varying Hamiltonian. The key challenge is estimating the minimum energy gap between the ground state and the first excited state of the interpolating Hamiltonian. This gap determines the required evolution time, which must be polynomial in the number of bits for the algorithm to be efficient. The paper discusses several examples, including a three-qubit example where the algorithm successfully finds the unique satisfying assignment of overlapping clauses. It also analyzes the Grover problem, which has a unique satisfying assignment and requires exponential time for the quantum adiabatic evolution, matching the performance of classical algorithms. The paper concludes that while the quantum adiabatic evolution can solve certain problems efficiently, the size of the minimum energy gap determines the algorithm's efficiency. For problems with a large gap, the algorithm runs in polynomial time, while for problems with a small gap, the required evolution time becomes impractically long. The paper also highlights that the structure of the problem plays a crucial role in determining the minimum gap and the efficiency of the algorithm.
Reach us at info@study.space