Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1311.2128 · New Journal of Physics

Commuting quantum circuits and complexity of Ising partition functions

Keisuke Fujii, Tomoyuki Morimae

Published Feb 10, 2017• 62 citations
arXivHTMLPDF

Abstract

Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to 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 calculating the imaginary-valued 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 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 partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.

DOI
10.1088/1367-2630/aa5fdb

Related papers

Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations

Michael J. Bremner, Ashley Montanaro, Dan J. Shepherd

We use the class of commuting quantum computations known as IQP (instantaneous quantum polynomial time) to strengthen the conjecture that quantum computers are hard to simulate classically. We show that, if either of two plausible average-case hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. One conjecture relates to the hardness of estimating the complex-temperature partition function for random instances of the Ising model; the other concerns approximating the number of zeroes of random low-degree polynomials. We observe that both conjectures can be shown to be valid in the setting of worst-case complexity. We arrive at these conjectures by deriving spin-based generalizations of the boson sampling problem that avoid the so-called permanent anticoncentration conjecture.

arXiv:1504.07999•Physical Review Letters•Aug 18, 2016•342 citations

Achieving quantum supremacy with sparse and noisy commuting quantum computations

Michael J. Bremner, Ashley Montanaro, Dan J. Shepherd

The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.

arXiv:1610.01808•Quantum•Apr 25, 2017•213 citations

Quantum algorithms for spin models and simulable gate sets for quantum computation

M. Van den Nest, Wolfgang Dür, Robert Raussendorf +1 more

We present simple mappings between classical lattice models and quantum circuits, which provide a systematic formalism to obtain quantum algorithms to approximate partition functions of lattice models in certain complex-parameter regimes. We, e.g., present an efficient quantum algorithm for the six-vertex model as well as a two-dimensional Ising-type model. We show that classically simulating these (complex-parameter) spin models is as hard as simulating universal quantum computation, i.e., BQP complete (BQP denotes bounded-error quantum polynomial time). Furthermore, our mappings provide a framework to obtain efficiently simulable quantum gate sets from exactly solvable classical models. We, e.g., show that the simulability of Valiant's match gates can be recovered by using the solvability of the free-fermion eight-vertex model.

arXiv:0805.1214•Physical Review A•Nov 30, 2009•41 citations

Quantum algorithm for an additive approximation of Ising partition functions

Akira Matsuo, Keisuke Fujii, Nobuyuki Imoto

We investigate quantum-computational complexity of calculating partition functions of Ising models. We construct a quantum algorithm for an additive approximation of Ising partition functions on square lattices. To this end, we utilize the overlap mapping developed by M. Van den Nest, W. D\"ur, and H. J. Briegel [Phys. Rev. Lett. 98, 117207 (2007)] and its interpretation through measurement-based quantum computation (MBQC). We specify an algorithmic domain, on which the proposed algorithm works, and an approximation scale, which determines the accuracy of the approximation. We show that the proposed algorithm performs a nontrivial task, which would be intractable on any classical computer, by showing that the problem that is solvable by the proposed quantum algorithm is BQP-complete. In the construction of the BQP-complete problem coupling strengths and magnetic fields take complex values. However, the Ising models that are of central interest in statistical physics and computer science consist of real coupling strengths and magnetic fields. Thus we extend the algorithmic domain of the proposed algorithm to such a real physical parameter region and calculate the approximation scale explicitly. We found that the overlap mapping and its MBQC interpretation improve the approximation scale exponentially compared to a straightforward constant-depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides partial evidence that there exist no efficient classical algorithm for a multiplicative approximation of the Ising partition functions even on the square lattice. This result supports the observation that the proposed quantum algorithm also performs a nontrivial task in the physical parameter region.

arXiv:1405.2749•Physical Review A•Aug 5, 2014•18 citations

Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy

Yuki Takeuchi, Yasuhiro Takahashi

Instantaneous quantum polynomial time (IQP) is a model of (probably) nonuniversal quantum computation. Since it has been proven that IQP circuits are unlikely to be simulated classically up to a multiplicative error and an error in the ${l}_{1}$ norm, IQP is considered as one of the promising classes that demonstrates quantum supremacy. Although IQP circuits can be realized more easily than a universal quantum computer, demonstrating quantum supremacy is still difficult. It is therefore desired to find subclasses of IQP that are easy to implement. In this paper, by imposing some restrictions on IQP, we propose ancilla-driven IQP (ADIQP) as the subclass of commuting quantum computation suitable for many experimental settings. We show that even though ADIQP circuits are strictly weaker than IQP circuits in a sense, they are also hard to simulate classically up to a multiplicative error and an error in the ${l}_{1}$ norm. Moreover, the properties of ADIQP make it easy to investigate the verifiability of ADIQP circuits and the difficulties in realizing ADIQP circuits.

arXiv:1611.00510•Physical Review A•Dec 27, 2016•6 citations

Quantum computation and combinatorial structures

Ryan L. Mann

This thesis explores the relationship between quantum computation and combinatorial structures, with the goal of improving our understanding of the complexity of quantum computation. We begin by studying the case when the complexity of combinatorial structures can be used to provide evidence for the hardness of classically simulating quantum computations. To this end, we show that the complexity of evaluating multiplicative-error approximations of Jones polynomials can be used to bound the classical complexity of simulating random quantum computations. We then proceed by studying the contrary case, that is, when do the combinatorial structures allow for an efficient classical simulation of quantum computations? We establish an efficient deterministic approximation algorithm for the Ising model partition function with complex parameters when the interactions and external fields are absolutely bounded close to zero. This provides an efficient classical algorithm for simulating a class of quantum computations with bounded interactions between the qubits. \nIn the second part of this thesis, we present some independent results on the efficient preparation of Fock states with a high number of photons from a resource of single photons. These Fock states are a fundamental resource in many quantum information protocols.

•Jan 1, 2019•0 citations
Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to 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 calculating the imaginary-valued 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 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 partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.
We use the class of commuting quantum computations known as IQP (instantaneous quantum polynomial time) to strengthen the conjecture that quantum computers are hard to simulate classically. We show that, if either of two plausible average-case hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. One conjecture relates to the hardness of estimating the complex-temperature partition function for random instances of the Ising model; the other concerns approximating the number of zeroes of random low-degree polynomials. We observe that both conjectures can be shown to be valid in the setting of worst-case complexity. We arrive at these conjectures by deriving spin-based generalizations of the boson sampling problem that avoid the so-called permanent anticoncentration conjecture.
The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(sqrt(n) log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.
We present simple mappings between classical lattice models and quantum circuits, which provide a systematic formalism to obtain quantum algorithms to approximate partition functions of lattice models in certain complex-parameter regimes. We, e.g., present an efficient quantum algorithm for the six-vertex model as well as a two-dimensional Ising-type model. We show that classically simulating these (complex-parameter) spin models is as hard as simulating universal quantum computation, i.e., BQP complete (BQP denotes bounded-error quantum polynomial time). Furthermore, our mappings provide a framework to obtain efficiently simulable quantum gate sets from exactly solvable classical models. We, e.g., show that the simulability of Valiant's match gates can be recovered by using the solvability of the free-fermion eight-vertex model.
We investigate quantum-computational complexity of calculating partition functions of Ising models. We construct a quantum algorithm for an additive approximation of Ising partition functions on square lattices. To this end, we utilize the overlap mapping developed by M. Van den Nest, W. D\"ur, and H. J. Briegel [Phys. Rev. Lett. 98, 117207 (2007)] and its interpretation through measurement-based quantum computation (MBQC). We specify an algorithmic domain, on which the proposed algorithm works, and an approximation scale, which determines the accuracy of the approximation. We show that the proposed algorithm performs a nontrivial task, which would be intractable on any classical computer, by showing that the problem that is solvable by the proposed quantum algorithm is BQP-complete. In the construction of the BQP-complete problem coupling strengths and magnetic fields take complex values. However, the Ising models that are of central interest in statistical physics and computer science consist of real coupling strengths and magnetic fields. Thus we extend the algorithmic domain of the proposed algorithm to such a real physical parameter region and calculate the approximation scale explicitly. We found that the overlap mapping and its MBQC interpretation improve the approximation scale exponentially compared to a straightforward constant-depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides partial evidence that there exist no efficient classical algorithm for a multiplicative approximation of the Ising partition functions even on the square lattice. This result supports the observation that the proposed quantum algorithm also performs a nontrivial task in the physical parameter region.
Instantaneous quantum polynomial time (IQP) is a model of (probably) nonuniversal quantum computation. Since it has been proven that IQP circuits are unlikely to be simulated classically up to a multiplicative error and an error in the l1{l}_{1}l1​ norm, IQP is considered as one of the promising classes that demonstrates quantum supremacy. Although IQP circuits can be realized more easily than a universal quantum computer, demonstrating quantum supremacy is still difficult. It is therefore desired to find subclasses of IQP that are easy to implement. In this paper, by imposing some restrictions on IQP, we propose ancilla-driven IQP (ADIQP) as the subclass of commuting quantum computation suitable for many experimental settings. We show that even though ADIQP circuits are strictly weaker than IQP circuits in a sense, they are also hard to simulate classically up to a multiplicative error and an error in the l1{l}_{1}l1​ norm. Moreover, the properties of ADIQP make it easy to investigate the verifiability of ADIQP circuits and the difficulties in realizing ADIQP circuits.
This thesis explores the relationship between quantum computation and combinatorial structures, with the goal of improving our understanding of the complexity of quantum computation. We begin by studying the case when the complexity of combinatorial structures can be used to provide evidence for the hardness of classically simulating quantum computations. To this end, we show that the complexity of evaluating multiplicative-error approximations of Jones polynomials can be used to bound the classical complexity of simulating random quantum computations. We then proceed by studying the contrary case, that is, when do the combinatorial structures allow for an efficient classical simulation of quantum computations? We establish an efficient deterministic approximation algorithm for the Ising model partition function with complex parameters when the interactions and external fields are absolutely bounded close to zero. This provides an efficient classical algorithm for simulating a class of quantum computations with bounded interactions between the qubits. \nIn the second part of this thesis, we present some independent results on the efficient preparation of Fock states with a high number of photons from a resource of single photons. These Fock states are a fundamental resource in many quantum information protocols.