Commuting quantum circuits and complexity of Ising partition functions
From MaRDI portal
Publication:6100591
Abstract: Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal in the sense of standard quantum computation. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy (PH) collapses at the third level, which is highly implausible. However, the origin of the classical intractability is still less understood. Here we establish a relationship between IQP and computational complexity of the partition functions of Ising models. We apply the established relationship in two opposite directions. One direction is to find subclasses of IQP that are classically efficiently simulatable in the strong sense, by using exact solvability of certain types of Ising models. Another direction is applying quantum computational complexity of IQP to investigate (im)possibility of efficient classical approximations of Ising models with imaginary coupling constants. Specifically, we show that there is no fully polynomial randomized approximation scheme (FPRAS) for Ising models with almost all imaginary coupling constants even on a planar graph of a bounded degree, unless the PH collapses at the third level. Furthermore, we also show a multiplicative approximation of such a class of Ising partition functions is at least as hard as a multiplicative approximation for the output distribution of an arbitrary quantum circuit.
Recommendations
- On complexity of the quantum Ising model
- A new connection between quantum circuits, graphs and the Ising partition function
- Complexity of commuting Hamiltonians on a square lattice of qubits
- Complexity classification of two-qubit commuting Hamiltonians
- Low depth quantum circuits for Ising models
- Complexity of reversible circuits and their quantum implementations
- Computational complexity of the quantum separability problem
- Complexity of stoquastic frustration-free Hamiltonians
- Computational complexity of uniform quantum circuit families and quantum Turing machines
- Algorithms and Computation
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1559533 (Why is no real title available?)
- scientific article; zbMATH DE number 1775384 (Why is no real title available?)
- A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
- A polynomial quantum algorithm for approximating the Jones polynomial
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- BQP and the polynomial hierarchy
- Classical Ising model test for quantum circuits
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
- Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
- Computational Complexity
- Diagonal-unitary 2-design and their implementations by quantum circuits
- Fault-tolerant quantum computation by anyons
- Generating a state \(t\)-design by diagonal quantum circuits
- Low depth quantum circuits for Ising models
- Matchgate and space-bounded quantum computations are equivalent
- Matchgates and classical simulation of quantum circuits
- On Unapproximable Versions of $NP$-Complete Problems
- PP is as Hard as the Polynomial-Time Hierarchy
- PP is closed under intersection
- Polynomial-Time Approximation Algorithms for the Ising Model
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Quantum algorithms for classical lattice models
- Quantum complexity theory
- Quantum computing and quadratically signed weight enumerators
- Quantum computing, postselection, and probabilistic polynomial-time
- Quantum information and statistical mechanics: an introduction to frontier
- Random measurement bases, quantum state distinction and applications to the hidden subgroup problem
- Statistical mechanics, three-dimensionality and NP-completeness
- Temporally unstructured quantum computation
- The Complexity of Ferromagnetic Ising with Local Fields
- The complexity of computing the permanent
- The computational complexity of linear optics
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
- Threshold Computation and Cryptographic Security
- Universal Blind Quantum Computation
- Universal linear optics
Cited in
(10)- Complexity classification of two-qubit commuting Hamiltonians
- Commuting quantum circuits with few outputs are unlikely to be classically simulatable
- Classical Ising model test for quantum circuits
- Quantum algorithms for classical lattice models
- Low depth quantum circuits for Ising models
- A new connection between quantum circuits, graphs and the Ising partition function
- The complexity of approximating complex-valued Ising and Tutte partition functions
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
- Suppressing weak Ising couplings: tailored gates for quantum computation
- Universal blind quantum computation for hybrid system
This page was built for publication: Commuting quantum circuits and complexity of Ising partition functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6100591)
