Circuit-to-Hamiltonian from tensor networks and fault tolerance

Anurag Anshu, Nikolas P. Breuckmann, Quynh T. Nguyen

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

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 an application, we 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.
Original languageEnglish
Title of host publicationSTOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery (ACM)
Pages585-595
Number of pages11
ISBN (Electronic)9798400703836
DOIs
Publication statusPublished - 11 Jun 2024
EventSTOC 2024: 56th Annual ACM Symposium on Theory of Computing - Vancouver, Canada
Duration: 24 Jun 202428 Jun 2024
https://acm-stoc.org/stoc2024/

Conference

ConferenceSTOC 2024: 56th Annual ACM Symposium on Theory of Computing
Country/TerritoryCanada
CityVancouver
Period24/06/2428/06/24
Internet address

Keywords

  • quant-ph
  • cs.CC

Fingerprint

Dive into the research topics of 'Circuit-to-Hamiltonian from tensor networks and fault tolerance'. Together they form a unique fingerprint.

Cite this