The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning

Abstract

We present a collection of results about the clock in Feynman's computer construction and Kitaev's Local Hamiltonian problem. First, by analyzing the spectra of quantum walks on a line with varying endpoint terms, we find a better lower bound on the gap of the Feynman Hamiltonian, which translates into a less strict promise gap requirement for the QMA-complete Local Hamiltonian problem. We also translate this result into the language of adiabatic quantum computation. Second, introducing an idling clock construction with a large state space but fast Cesaro mixing, we provide a way for achieving an arbitrarily high success probability of computation with Feynman's computer with only a logarithmic increase in the number of clock qubits. Finally, we tune and thus improve the costs (locality, gap scaling) of implementing a (pulse) clock with a single excitation.

32 pages; v2: typos, references, and minor fixes, close to the published version

References in corpus (7)

• The density-matrix renormalization group in the age of matrix product states
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Exponential algorithmic speedup by quantum walk
• Bounds for the adiabatic approximation with applications to quantum computation
• A new construction for a QMA complete 3-local Hamiltonian
• Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
• Method to identify parent Hamiltonians for trial states

Cited by in corpus (19)

• Noncausal Page-Wootters circuits
• How fast do quantum walks mix?
• Importance of the spectral gap in estimating ground-state energies
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Variational dynamics as a ground-state problem on a quantum computer
• Hamiltonian quantum computing with superconducting qubits
• Quantum advantage from energy measurements of many-body quantum systems
• Detailed Analysis of Circuit-to-Hamiltonian Mappings
• Limit theorems and localization of three state quantum walks on a line defined by generalized Grover coins
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• Simulating quantum circuits by adiabatic computation: improved spectral gap bounds
• Classifying Data with Local Hamiltonians
• Quantum Path Computing: Computing Architecture with Propagation Paths in Multiple Plane Diffraction of Classical Sources of Fermion and Boson Particles
• Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
• The 7 faces of quantum NP
• Approximate low-weight check codes and circuit lower bounds for noisy ground states
• Relational Dynamics with Periodic Clocks
• The Complexity of Approximating Critical Points of Quantum Phase Transitions
• An Empirical Study of Quantum Dynamics as a Ground State Problem with Neural Quantum States