Quantum Commuting Circuits and Complexity of Ising Partition Functions

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.

36 pages, 5 figures

References in corpus (16)

• Universal Linear Optics
• Photonic Boson Sampling in a Tunable Circuit
• Efficient experimental validation of photonic boson sampling against the uniform distribution
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Experimental Scattershot Boson Sampling
• On the experimental verification of quantum complexity in linear optics
• Matchgates and classical simulation of quantum circuits
• Simple universal models capture all classical spin physics
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• On measurement-based quantum computation with the toric code states
• Completeness of the classical 2D Ising model and universal quantum computation
• Generating a state $t$-design by diagonal quantum circuits
• Diagonal quantum circuits: their computational power and applications
• On the Quantum Computational Complexity of the Ising Spin Glass Partition Function and of Knot Invariants
• A quantum algorithm for additive approximation of Ising partition functions

Cited by in corpus (31)

• Characterizing Quantum Supremacy in Near-Term Devices
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Computational advantage of quantum random sampling
• Efficient Quantum Walk on a Quantum Processor
• Architectures for quantum simulation showing a quantum speedup
• Verified measurement-based quantum computing with hypergraph states
• Anticoncentration theorems for schemes showing a quantum speedup
• Variational inference with a quantum computer
• From estimation of quantum probabilities to simulation of quantum circuits
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Progress toward favorable landscapes in quantum combinatorial optimization
• Fast estimation of outcome probabilities for quantum circuits
• Simulating noisy variational quantum eigensolver with local noise models
• The principle of majorization: application to random quantum circuits
• Nonadaptive fault-tolerant verification of quantum supremacy with noise
• Sharp complexity phase transitions generated by entanglement
• Robust sparse IQP sampling in constant depth
• Emulating Quantum Interference with Generalized Ising Machines
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• Simulating Quantum Computations with Tutte Polynomials
• Quantifying multiparticle entanglement with randomized measurements
• Finding resource states of measurement-based quantum computing is harder than quantum computing
• Phase context decomposition of diagonal unitaries for higher-dimensional systems
• Computational quantum-classical boundary of complex and noisy quantum systems
• Quantum estimation bound of Gaussian matrix permanent