Space-Time Circuit-to-Hamiltonian Construction and Its Applications

Abstract

The circuit-to-Hamiltonian construction translates dynamics (a quantum circuit and its output) into statics (the groundstate of a circuit Hamiltonian) by explicitly defining a quantum register for a clock. The standard Feynman-Kitaev construction uses one global clock for all qubits while we consider a different construction in which a clock is assigned to each interacting qubit. This makes it possible to capture the spatio-temporal structure of the original quantum circuit into features of the circuit Hamiltonian. The construction is inspired by the original two-dimensional interacting fermionic model (see http://link.aps.org/doi/10.1103/PhysRevA.63.040302) We prove that for one-dimensional quantum circuits the gap of the circuit Hamiltonian is appropriately lower-bounded, partially using results on mixing times of Markov chains, so that the applications of this construction for QMA (and partially for quantum adiabatic computation) go through. For one-dimensional quantum circuits, the dynamics generated by the circuit Hamiltonian corresponds to diffusion of a string around the torus.

27 pages, 5 figures

References in corpus (4)

• Universal computation by multi-particle quantum walk
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• The power of quantum systems on a line
• Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians

Cited by in corpus (23)

• Adiabatic Quantum Computing
• Quantum Low-Density Parity-Check Codes
• Balanced Product Quantum Codes
• Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
• Undecidability of the Spectral Gap in One Dimension
• Local tests of global entanglement and a counterexample to the generalized area law
• Noncausal Page-Wootters circuits
• Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• Adiabatic and Hamiltonian computing on a 2D lattice with simple 2-qubit interactions
• Analysis and limitations of modified circuit-to-Hamiltonian constructions
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Non-Unitary Quantum Computation in the Ground Space of Local Hamiltonians
• Error Suppression for Hamiltonian Quantum Computing in Markovian Environments
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
• The complexity of simulating local measurements on quantum systems
• Hamiltonian quantum computing with superconducting qubits
• Proof of efficient, parallelized, universal adiabatic quantum computation
• Circuit-to-Hamiltonian from tensor networks and fault tolerance
• Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
• Relational Dynamics with Periodic Clocks
• Improving adiabatic quantum factorization via chopped random-basis optimization
• Complexity of Fermionic 2-SAT