Circuit-to-Hamiltonian from tensor networks and fault tolerance

Abstract

We define a map from an arbitrary quantum circuit to a local Hamiltonian whose ground state encodes the quantum computation. All previous maps relied on the Feynman-Kitaev construction, which introduces an ancillary `clock register' to track the computational steps. Our construction, on the other hand, relies on injective tensor networks with associated parent Hamiltonians, avoiding the introduction of a clock register. This comes at the cost of the ground state containing only a noisy version of the quantum computation, with independent stochastic noise. We can remedy this - making our construction robust - by using quantum fault tolerance. In addition to the stochastic noise, we show that any state with energy density exponentially small in the circuit depth encodes a noisy version of the quantum computation with adversarial noise. We also show that any `combinatorial state' with energy density polynomially small in depth encodes the quantum computation with adversarial noise. This serves as evidence that any state with energy density polynomially small in depth has a similar property. As applications, we give a new proof of the QMA-completeness of the local Hamiltonian problem (with logarithmic locality) and show that contracting injective tensor networks to additive error is BQP-hard. We also discuss the implication of our construction to the quantum PCP conjecture, combining with an observation that QMA verification can be done in logarithmic depth.

arXiv commentAppeared in QIP 2024 and STOC 2024; version 2 included a proof of QMA-completeness and expanded discussions

References in corpus (11)

• A simple nearest-neighbor two-body Hamiltonian system for which the ground state is a universal resource for quantum computation
• Rapid adiabatic preparation of injective PEPS and Gibbs states
• Preparing projected entangled pair states on a quantum computer
• Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems
• Local tests of global entanglement and a counterexample to the generalized area law
• Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians
• Space-Time Circuit-to-Hamiltonian Construction and Its Applications
• Approximating local observables on projected entangled pair states
• A construction of Combinatorial NLTS
• Circuit-to-Hamiltonian from tensor networks and fault tolerance
• Approximate low-weight check codes and circuit lower bounds for noisy ground states

Cited by in corpus (3)

• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• When Federated Learning Meets Quantum Computing: Survey and Research Opportunities
• Circuit-to-Hamiltonian from tensor networks and fault tolerance