Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Fast Quantum Algorithms for Traversing Paths of Eigenstates

Published

Author(s)

S. Boixo, Emanuel Knill, Rolando Somma

Abstract

Consider a path of non-degenerate eigenstates |psi_s>, 0<= s<= 1 of unitary operators U_s or Hamiltonians H_s with minimum eigenvalue gap Δ. The eigenpath traversal problem is to transform one or more copies of |psi_0> to |psi_1> Solutions to this problem have applications ranging from quantum physics simulation to optimization. For Hamiltonians, the conventional way of doing this is by applying the adiabatic theorem. We give ''digital'' methods for performing the transformation that require no assumption on path continuity or differentiability other than the absence of large jumps. Given sufficient information about eigenvalues and overlaps between states on the path, the transformation can be accomplished with complexity O((L/Δ) log(L/epsilon)), where L is the angular length of the path and epsilon is a specified bound on the error of the output state. We show that the required information can be obtained in a first set of transformations, whose complexity per state transformed has an additional factor that depends logarithmically on a maximum angular velocity along the path. This velocity is averaged over constant angular distances and does not require continuity. Our methods have substantially better behavior than conventional adiabatic algorithms, with fewer conditions on the path. They also improve on the previously best digital methods and demonstrate that path length is the primary parameter that determines the complexity of state transformation along a path.
Citation
Quantum Information & Computation

Keywords

quantum computing, quantum algorithms, adiabatic methods

Citation

Boixo, S. , Knill, E. and Somma, R. (2010), Fast Quantum Algorithms for Traversing Paths of Eigenstates, Quantum Information & Computation, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=905112 (Accessed December 3, 2023)
Created May 16, 2010, Updated October 12, 2021