Commuting quantum circuits and complexity of Ising partition functions
From MaRDI portal
(Redirected from 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
- 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
- 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?)
- 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
- Polynomial-Time Approximation Algorithms for the Ising Model
- PP is as Hard as the Polynomial-Time Hierarchy
- PP is closed under intersection
- Quantum algorithms for classical lattice models
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- 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 computing the permanent
- The Complexity of Ferromagnetic Ising with Local Fields
- 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)- A new connection between quantum circuits, graphs and the Ising partition function
- Suppressing weak Ising couplings: tailored gates for quantum computation
- The complexity of approximating complex-valued Ising and Tutte partition functions
- Universal blind quantum computation for hybrid system
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
- Commuting quantum circuits with few outputs are unlikely to be classically simulatable
- Low depth quantum circuits for Ising models
- Classical Ising model test for quantum circuits
- Quantum algorithms for classical lattice models
- Complexity classification of two-qubit commuting Hamiltonians
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)
