Over the last decades, there have been many proposals for quantum computation. One of the promising candidates is adiabatic quantum computation (AQC). The central idea of AQC is about finding the ground state of a system with a problem Hamiltonian via particular adiabatic passages, starting from an initialized ground state of a simple Hamiltonian. One disadvantage of AQC is the significant growth of necessary runtime, in particular when there are quantum phase transitions during the AQC passages. Here we propose a nondeterministic ground state cooling quantum computation model based on selective projection measurements on an ancilla coupled to the system with the problem Hamiltonian previously cooled by conventional techniques. We illustrate the model by Grover search problem and show that our nondeterministic model requires a constant or at most logarithmic runtime and can also get rid of possible difficulties in preparing the ground state of the simple Hamiltonian.
Over the last decades, there have been many proposals for quantum computation. One of the promising candidates is adiabatic quantum computation (AQC). The central idea of AQC is about finding the ground state of a system with a problem Hamiltonian via particular adiabatic passages, starting from an initialized ground state of a simple Hamiltonian. One disadvantage of AQC is the significant growth of necessary runtime, in particular when there are quantum phase transitions during the AQC passages. Here we propose a nondeterministic ground state cooling quantum computation model based on selective projection measurements on an ancilla coupled to the system with the problem Hamiltonian previously cooled by conventional techniques. We illustrate the model by Grover search problem and show that our nondeterministic model requires a constant or at most logarithmic runtime and can also get rid of possible difficulties in preparing the ground state of the simple Hamiltonian.
Adiabatic quantum computation (AQC) is a universal model for quantum computation which seeks to transform the initial ground state of a quantum system into a final ground state encoding the answer to a computational problem. AQC initial Hamiltonians conventionally have a uniform superposition as ground state. We diverge from this practice by introducing a simple form of heuristics: the ability to start the quantum evolution with a state which is a guess to the solution of the problem. With this goal in mind, we explain the viability of this approach and the needed modifications to the conventional AQC (CAQC) algorithm. By performing a numerical study on hard-to-satisfy 6 and 7 bit random instances of the satisfiability problem (3-SAT), we show how this heuristic approach is possible and we identify that the performance of the particular algorithm proposed is largely determined by the Hamming distance of the chosen initial guess state with respect to the solution. Besides the possibility of introducing educated guesses as initial states, the new strategy allows for the possibility of restarting a failed adiabatic process from the measured excited state as opposed to restarting from the full superposition of states as in CAQC. The outcome of the measurement can be used as a more refined guess state to restart the adiabatic evolution. This concatenated restart process is another heuristic that the CAQC strategy cannot capture.
The adiabatic quantum computation (AQC) has been proven to be equivalent to the standard circuit model. Conventionally, AQC evolves from the initial Hamiltonian which has a uniform equal superposition of the computational basis to the final Hamiltonian whose ground state encodes the solution to a computation problem. We propose an alternative approach to construct the initial Hamiltonian of the AQC which has an unequal superposition of the possible solutions to the problem and show that an educated guess can improve the performance of AQC.
Quantum adiabatic optimization (QAO) is performed using a time-dependent Hamiltonian H(s) with spectral gap γ(s). Assuming the existence of an oracle Γ such that $γ_\min = Θ\left(\min_sΓ(s)\right)$, we provide an algorithm that reliably performs QAO in time $O\left(γ_\min^{-1}\right)$ with $O\left(\log(γ_\min^{-1})\right)$ oracle queries, where $γ_\min = \min_s γ(s)$. Our strategy is not heuristic and does not require guessing time parameters or annealing paths. Rather, our algorithm naturally produces an annealing path such that ∥dH/ds∥≈γ(s) and chooses its own runtime to be as close as possible to optimal while promising convergence to the ground state. We then demonstrate the feasibility of this approach in practice by explicitly constructing a gap oracle Γ for the problem of finding the minimum point m=argminuW(u) of the cost function W:V⟶[0,1], restricting ourselves to computational basis measurements and driving Hamiltonian H(0)=I−∣V∣−1∑u,v∈V∣u⟩⟨v∣. Requiring only that W have a constant lower bound on its spectral gap and upper bound κ on its spectral ratio, our QAO algorithm returns m with probability (1−ε)(1−e−1/ε) in time O(ε−1[∣V∣+(κ−1)2/3∣V∣2/3]). This achieves a quantum advantage for all κ, and recovers Grover scaling up to logarithmic factors when κ≈1. We implement the algorithm as a subroutine in an optimization procedure that produces m with exponentially small failure probability and expected runtime O(ε−1[∣V∣+(κ−1)2/3∣V∣2/3]) even when κ is not known beforehand.
QUBO problems are NP-hard and have wide applications in optimization, including finance, logistics, machine learning, and combinatorial problems. However, classical algorithms employed for solving them can often get stuck in local minima. This paper presents an Adiabatic Quantum Computing (AQC) approach towards finding an optimal solution for QUBO problems. The QUBO problem has been first encoded into Hamiltonians. The adiabatic theorem has been used to achieve success of an AQC solution with a rate which is found to be dependent on relative gap between the ground state and first exited state of the Hamiltonian.
Grover's search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle -- a black-box unitary operation. Generation of this oracle is formally beyond the original algorithm design. Here, we propose a realization of Grover's oracle for a large class of searching problems using a quantum annealing step. The time of this step grows only logarithmically with the size of the database. This suggests an efficient path to application of Grover's algorithm to practically important problems, such as finding the ground state of a Hamiltonian with a spectral gap over its ground state.
Quantum computation by the adiabatic theorem requires a slowly-varying Hamiltonian with respect to the spectral gap. We show that the Landau–Zener–Stückelberg oscillation phenomenon, which naturally occurs in quantum two-level systems under non-adiabatic periodic drive, can be exploited to find the ground state of an N-dimensional Grover Hamiltonian. The total runtime of this method is O ( 2 n ) , which is equal to the computational time of the Grover algorithm in the quantum circuit model. An additional periodic drive can suppress a large subset of Hamiltonian control errors by using coherent destruction of tunneling, thus outperforming previous algorithms.