Average-case complexity versus approximate simulation of commuting quantum computations

By Michael J. Bremner, Ashley Montanaro, D. Shepherd. Physical Review Letters, 2015

315 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/b9c2af4f46f9eda5c7796439ec52dd8c9f7da389

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

In Statistics and Probability

Citations in the corpus

Simulation of quantum circuits by low-rank stabilizer decompositions (2018, unknown): “[15]).”
Quantum advantage with shallow circuits (2017, background): “…a shift in our approach to quantummechanical systems: Modern quantum information science seeks to exploit quantum phenomena such as nonlocality, entanglement, and the superposition principle to tackle information-processing tasks that are believed to be difficult or impossible to achieve by…”
Quantum Supremacy through the Quantum Approximate Optimization Algorithm (2016, background): “This can be done for certain models of quantum computing [3,12] but subject to additional conjectures from complexity theory and/or probability theory.”
Quantum circuits and low-degree polynomials over F2 (2016, background): “More recently, together with Bremner and Shepherd [11], the present author used a correspondence between low-degree polynomials and a certain class of simple quantum computations, known as IQP circuits [37], to argue that random IQP circuits are unlikely to be eﬃciently simula-ble classically.”
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017, background): “Results for IQP circuits, whose close structural similarities with QAOA circuits have already provided insights [17], and whose advanced status with respect to error analysis and fault tolerance [47, 48] are likely to prove especially useful.”
Strawberry Fields: A Software Platform for Photonic Quantum Computing (2018, background): “Efficient classical sampling of the resulting probability distribution H⊗N UH⊗N |0〉 — even approximately [13] or in the presence of noise [91]— has been shown to be #P-hard, and would result in the collapse of the polynomial hierarchy to the third level [12, 92].”
Quantum computational supremacy (2017, background): “Second, and less obviously, they allow us to rule out a larger class of classical simulations.(9,19,20) Suppose the quantum circuit outputs string z with probability q(z) and a classical simulator does so with probability p(z).”
Quantum computational advantage using photons (2020, methodology): “n perform the same task in a reasonable amount of time and is unlikely overturned by classical algorithmic or hardware improvements, it was called quantum computational advantage or quantum supremacy (7, 8). Here, we use the first term. A very recent experiment on a quantum processor with 53 superco”
Logical quantum processor based on reconfigurable atom arrays (2023, methodology): “Sampling from the output distribution of such circuits is known to be classically hard in certain instances 20 , implying that a quantum device can be exponentially faster than a classical computer for this task.”