A Caltech Library Service

Analysis and limitations of modified circuit-to-Hamiltonian constructions

Bausch, Johannes and Crosson, Elizabeth (2018) Analysis and limitations of modified circuit-to-Hamiltonian constructions. Quantum, 2 . Art. No. 94. ISSN 2521-327X.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the Ω(T^(−2))Ω scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits. Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight O(T^(−2)) upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the Ω(T^(−3)) scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the O(T^(−2)) bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Alternate Title:Increasing the quantum UNSAT penalty of the circuit-to-Hamiltonian construction
Additional Information:© 2018 This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. Published: 2018-09-19. J. B. acknowledges support from the German National Academic Foundation, the EPSRC (grant 1600123), and the Draper's Research Fellowship at Pembroke College. E. C. acknowledges support provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). J. B. would also like to thank Thomas Vidick and the IQIM for hospitality during spring 2016 and summer 2017. We thank Toby Cubitt for useful discussions regarding section 5.2.1 and appendix A.2.
Group:IQIM, Institute for Quantum Information and Matter
Funding AgencyGrant Number
Studienstiftung des deutschen VolkesUNSPECIFIED
Engineering and Physical Sciences Research Council (EPSRC)1600123
Pembroke CollegeUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Record Number:CaltechAUTHORS:20171102-114342542
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:82893
Deposited By: Bonnie Leung
Deposited On:02 Nov 2017 19:16
Last Modified:20 Feb 2019 23:31

Repository Staff Only: item control page