Commuting quantum circuits and complexity of Ising partition functions

DOI10.1088/1367-2630/AA5FDBzbMATH Open1514.81091arXiv1311.2128OpenAlexW3099752579MaRDI QIDQ6100591FDOQ6100591

Authors: Keisuke Fujii, Tomoyuki Morimae 

Publication date: 12 May 2023

Published in: New Journal of Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1311.2128

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

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites Work

• Title not available (Why is that?)
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Title not available (Why is that?)
• Computational Complexity
• Quantum computing, postselection, and probabilistic polynomial-time
• The complexity of computing the permanent
• Fault-tolerant quantum computation by anyons
• Universal Blind Quantum Computation
• A polynomial quantum algorithm for approximating the Jones polynomial
• Polynomial-Time Approximation Algorithms for the Ising Model
• The Complexity of Ferromagnetic Ising with Local Fields
• On Unapproximable Versions of $NP$-Complete Problems
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Quantum complexity theory
• The computational complexity of linear optics
• Statistical mechanics, three-dimensionality and NP-completeness
• Title not available (Why is that?)
• PP is as Hard as the Polynomial-Time Hierarchy
• Low depth quantum circuits for Ising models
• Classical Ising model test for quantum circuits
• Quantum algorithms for classical lattice models
• PP is closed under intersection
• BQP and the polynomial hierarchy
• Generating a state \(t\)-design by diagonal quantum circuits
• Quantum computing and quadratically signed weight enumerators
• Title not available (Why is that?)
• Matchgates and classical simulation of quantum circuits
• Threshold Computation and Cryptographic Security
• Random measurement bases, quantum state distinction and applications to the hidden subgroup problem
• Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
• A linear-optical proof that the permanent is \(\#\mathrm{P}\)-hard
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
• Temporally unstructured quantum computation
• Matchgate and space-bounded quantum computations are equivalent
• Quantum information and statistical mechanics: an introduction to frontier
• Universal linear optics
• Diagonal-unitary 2-design and their implementations by quantum circuits

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)