Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model

• The model is classically intractable to multiplicative errors under stated complexity-theoretic assumptions.The supplemental proof is based on complexity results.Source: SUPPLEMENTAL MATERIAL · p. 6
• Variation-distance hardness follows if the relevant worst-case results can be strengthened to average-case hardness.Source: SUPPLEMENTAL MATERIAL · p. 6
• The supplemental material gives a certification method for the quantum sampler under sufficiently small measurement imperfections.Source: SUPPLEMENTAL MATERIAL · p. 6

• NP contains efficiently verifiable yes-instances, while #P counts accepting witnesses and the polynomial hierarchy generalizes NP through alternating quantifiers.Source: Related Complexity Results · pp. 6–7
• The analysis uses postBQP for postselected quantum computation and postBPP as its classical analogue.Source: Related Complexity Results · p. 7
• The proof adopts the postselection-register formulation in which selected measurement outcomes replace an all-zero postselection string.Source: Related Complexity Results · p. 7
• A fixed completeness–soundness gap in the Ising problem induces a nonzero gap for the classical BPP simulator.Source: Related Complexity Results · p. 8
• Postselected Ising computation can simulate a universal quantum computer, yielding the key bridge to postBQP.Source: Related Complexity Results · p. 8
• Efficient classical simulation would imply a collapse of the polynomial hierarchy, contradicting its standard non-collapse conjecture.The argument combines postselected Ising simulation with complexity-class containments.Source: Related Complexity Results · p. 8

• Choosing measurement angles implements arbitrary single-qubit gates and the CNOT gate, which together are universal.The construction combines these gates across the brickwork state to realize universal quantum computation.Source: Universal Quantum Computation with the… · p. 8

• The construction organizes these corrections into three separate cases for absorbing extra magnetic fields.Source: MAGNETIC FIELD IN THE ISING SPIN MODEL · p. 8
• Boundary spins with one coupling carry Rz(π/2), which is canceled by applying Rz(−π/2) to the remaining circuit.Source: MAGNETIC FIELD IN THE ISING SPIN MODEL · p. 8
• Spins with two couplings carry Rz(π), which is equivalent to an extra Z gate removed by flipping the measurement result.Source: MAGNETIC FIELD IN THE ISING SPIN MODEL · p. 8
• Spins with three couplings carry Rz(3π/2); the rotation is absorbed by changing θ and updating measurement results s2 and s3.The angle is adjusted to π/8 + 3π/2 = π/8 −π/2 mod 2π.Source: MAGNETIC FIELD IN THE ISING SPIN MODEL · p. 8

break and bridge operations

• Measuring a rotated cluster qubit in the Z basis implements the break operation, while X-basis measurement implements the bridge operation.The qubit is first rotated by Rz(π/2); postselecting |0⟩ gives the identity operation, whereas postselecting |+⟩ yields the Ising-interaction evolution.Source: break and bridge operations · pp. 8–9
• The brickwork state supports universal quantum computation through suitable single-qubit and two-qubit gate constructions.Source: Figure 3 · p. 9
• Break and bridge operations reduce a two-dimensional cluster state to graph states such as the brickwork state.Source: break and bridge operations · p. 9

Simulation with variation Distance Errors

• The technical complexity analysis first establishes a worst-case-hard problem before lifting that hardness to the average-case setting.Source: Simulation with variation Distance… · p. 9

A #P-hard problem in worst-case

• The sampler probability qx is linked to a polynomial-size circuit amplitude, with a factor 1/2^(mn−m) arising from equal measurement probabilities.Source: A #P-hard problem in worst-case · pp. 9–10
• Approximating qx to the stated multiplicative error is #P-hard for any constant 0 ≤ c < 1/2.Source: A #P-hard problem in worst-case · p. 10
• The proof reduces approximation of squared gap values to the sampler problem, using the integrality of gap(f)^2 to recover exact zero versus nonzero cases.Source: A #P-hard problem in worst-case · pp. 10–11
• The hardness construction uses an imaginary-temperature partition function with β ≡ 1/kBT = i and rewrites the result in partition-function form.Source: A #P-hard problem in worst-case · p. 11
• Approximating the partition function within the stated error is #P-hard in the worst case for 0 ≤ c < 1/2.Source: A #P-hard problem in worst-case · p. 11

Classically-intractable for simulation with variation distance error

• Stockmeyer’s theorem provides an FBPP^NP multiplicative approximation for probabilities generated by efficient classical samplers.Source: Classically-intractable for simulation… · p. 11
• Variation-distance closeness combined with Markov’s inequality yields a mixture of multiplicative and additive probability errors for many outcomes.Source: Classically-intractable for simulation… · pp. 11–12
• Worst-case #P-hardness plus the average-case assumption implies that a classical variation-distance sampler would give a BPP^NP algorithm for #P-hard problems.Source: Classically-intractable for simulation… · p. 12
• If partition-function approximation remains #P-hard for a 1−δ fraction of instances, variation-distance simulation is classically intractable unless the polynomial hierarchy collapses.Source: Classically-intractable for simulation… · p. 12

Intuition of our average-case hardness conjecture

• Random 2-qubit gates in C_x use independently chosen angles from eight multiples of π/4, defining the circuit ensemble for the conjecture.The circuit is formed layer by layer, with n layers and only boundary single-qubit exceptions.Source: Intuition of our average-case hardness… · p. 12, Figure 5 · p. 13
• If either δ or δ′ is not 0 or π, a gate can entangle some product states, and these circuits are conjectured likely to produce highly entangled states.The entanglement observation motivates treating the ensemble as sufficiently random for average-case hardness.Source: Intuition of our average-case hardness… · p. 12
• The conjecture states that approximating amplitudes of these random circuits to the error in Eq. (34) is #P-hard on average.This is presented as a conjecture rather than an established theorem.Source: Intuition of our average-case hardness… · p. 12
• The ensemble is compared with random quantum-circuit sampling, where sufficient depth is associated with Porter–Thomas output statistics and average-case hardness.The paper expects its distribution to approach Porter–Thomas behavior when n is comparable to m.Source: Intuition of our average-case hardness… · p. 12

Certification to variation Distance Errors

• Local measurement imperfections can be controlled when each spin’s error is below ε = ϵm/(mn), guaranteeing total measurement error at most ϵm.The assumption is that measurement errors are local and sufficiently small.Source: Certification to variation Distance… · p. 13
• The total variation-distance error is decomposed into state-preparation error D(ρ, ρ′) and measurement error D(E(ρ′), E′(ρ′)).The first term covers evolution and initial-state preparation, while the second covers imperfect measurements.Source: Certification to variation Distance… · p. 13
• The preparation-error bound is reduced to testing whether the laboratory state is close to the unique ground state of a local gapped Hamiltonian.The protocol estimates local Hamiltonian terms and uses them to estimate fidelity with the ideal ground state.Source: Certification to variation Distance… · p. 14
• For the brickwork Hamiltonian, J = 1 and ∆ = 1, and choosing ϵd = O(ϵ), ϵm = O(ϵ), and ϵ′ = O(ϵ^2) requires M = O(m^2n^2r/ϵ^4) measurements per local term.The resulting confidence level is 1 − 2^-O(r), so the certification protocol is efficient.Source: Certification to variation Distance… · p. 14

Hardness of Classically Simulating the Square Lattice Model to variation Distance Errors

• For Z measurements on qubit 0, outcomes |0⟩ and |1⟩ occur with probability 1/2, and the |1⟩ outcome flips measurement results on blue circles.The corresponding operation is iZ1 ⊗ Z2.Source: Hardness of Classically Simulating the… · p. 14
• For X measurements on qubit 0, outcomes |+⟩ and |−⟩ likewise occur with probability 1/2, with the |−⟩ outcome also inducing a blue-circle result flip.This supplies the analogous correction rule for the bridge operation.Source: Hardness of Classically Simulating the… · p. 14
• Given red-circle outcomes y, the blue-circle result x and intermediate result x′ determine each other, while q_y = 1/2^r and q_{x′|y} = q_x.Here r is the number of red circles, r = 3mn − 2m − 2n + 1.Source: Hardness of Classically Simulating the… · p. 14
• A classical sampler for the square-lattice distribution can therefore be converted into one for the brickwork model by outputting x determined from (x′, y).The paper concludes that the square-lattice hardness result follows under the same conjectures, including noncollapse of the polynomial hierarchy and Theorem 4.Source: Hardness of Classically Simulating the… · p. 15