On optimal methods for adiabatic quantum state transformations

Many problems in science could be solved by preparing the low-energy quantum state (or any eigenstate) of a Hamiltonian. A common example is the Boolean satisfiability problem, where each clause can be mapped to the energy of an interacting many-body system, and the problem reduces to minimizing the energy. In quantum computing, adiabatic quantum state transformations (ASTs) provide a tool for preparing the quantum state. ASTs are conventionally implemented via slow or adiabatic perturbations to the Hamiltonian, relying on the quantum adiabatic theorem. Nevertheless, more efficient implementations of ASTs exist. In this talk I will review recently developed methods for ASTs that are more efficient and require less assumptions on the Hamiltonians than the conventional implementation [1,2]. Such methods involve measurements of the states along the evolution path and have a best-case implementation cost of L/G, where L is the length of the (evolved) state path and G is a lower bound to the spectral gap of the Hamiltonians. I will show that this cost is optimal [3] and comment on results of the gap amplification problem, where the goal is to reduce the cost by increasing G [4].\\[4pt] [1] S. Boixo, E. Knill, and R.D. Somma, ``Quantum state preparation by phase randomization,'' Quant. Inf. Comp. 9, 833 (2009).\\[0pt] [2] S. Boixo, E. Knill, and R.D. Somma, ``Fast quantum algorithms for traversing paths of eigenstates,'' e-print arXiv:1005.3034 (2010).\\[0pt] [3] R.D. Somma and S. Boixo, ``Necessary condition for the quantum adiabatic approximation,'' Phys. Rev. A 81, 032308 (2010).\\[0pt] [4] R.D. Somma and S. Boixo, ``Spectral gap amplification,'' SIAM J. Comp. (2012).