PaperlayerView exact revision on arXiv

Source-linked AI summary

Instantaneous Quantum Computation

Dan Shepherd, Michael J. Bremner

arXiv:0809.0847v3quant-ph

TL;DR

The paper asks whether quantum computation can be verified more simply than tomography or Shor-style demonstrations. It develops instantaneous quantum computation and BPPIQP oracle models, arguing for classically hard sampling and interactive proof protocols, while acknowledging important open limitations.

  • Problem

    Verifying growing quantum computers is difficult because tomography scales poorly, while convincing Shor demonstrations require more than a thousand logical qubits.

  • Method

    The paper models commuting X-program Hamiltonians with computational-basis measurements and augments classical randomized computation with an IQP sampling oracle.

  • Results

    The paper argues that IQP distributions are hard to sample approximately classically and presents polynomial-time interactive protocols believed to resist classical completion.

  • Takeaways & Limitations

    IQP can support interactive proof games for demonstrating quantum effects, including a test distinguishing approximately 85.4% quantum from 75% classical orthogonality outcomes.

  • Takeaways & Limitations

    The testing concept does not provide secret data or an NP witness, and finding a more computation-like BPPIQP task remains open.

Abstract

from arXiv · show

We examine theoretic architectures and an abstract model for a restricted class of quantum computation, called here instantaneous quantum computation because it allows for essentially no temporal structure within the quantum dynamics. Using the theory of binary matroids, we argue that the paradigm is rich enough to enable sampling from probability distributions that cannot, classically, be sampled from efficiently and accurately. This paradigm also admits simple interactive proof games that may convince a skeptic of the existence of truly quantum effects. Furthermore, these effects can be created using significantly fewer qubits than are required for running Shor's Algorithm.

1 Introduction

The paper introduces IQP, a restricted quantum-computation paradigm with essentially no temporal structure, and develops it as a possible route to verifying quantum behavior with simpler devices than Shor factoring. It motivates IQP through classically hard sampling and interactive proof protocols, while acknowledging unresolved computational and architectural limitations.

  • Motivation and paradigm: IQP restricts quantum computation to abelian dynamics, placing it between classical and universal quantum computing.The restriction removes much of the non-abelian structure associated with universal circuit models.
  • Motivation and paradigm: Tomography becomes difficult as systems grow, motivating simpler ways to verify whether a quantum computation has succeeded.The paper frames solving classically difficult problems as one possible verification strategy.
  • Motivation and paradigm: Shor-based verification may require more than a thousand logical qubits and a fully universal gate set for a convincing demonstration.The paper notes that Shor’s algorithm is comparatively difficult to implement despite several depth-width trade-offs.
  • Contributions: The paper proposes an abelian-dynamics two-party protocol for remotely testing a quantum device, conjecturing that it is classically infeasible to simulate.The protocol is intended to be physically simpler than factorization and does not require a universal gate set.
  • Contributions: The authors define IQP, present multiple architectures, and argue that IQP distributions and associated protocols may resist efficient classical simulation.The architectures include graph-state ideas and are presented as natural realizations of the restricted model.
  • Limitations: The proposed protocol is described as a simple proof of distinctly quantum behavior, but its separation from classical computation relies on computational-hardness conjectures.The paper also reports that no decision language in BPPIQP is known to lie outside BPP.

2 The IQP paradigm

The IQP paradigm is formalized through commuting X-program Hamiltonians whose outputs are computational-basis samples, with oracle access defined abstractly. For constant-action programs, binary codes and matroids characterize directional output bias, while special angles yield trivial or classically simulable distributions.

  • X-programs: An X-program is a polynomial-size list of commuting Pauli-X products applied to selected qubits, so program-element ordering is irrelevant.The qubits start in |0⟩ and are measured in the computational basis after the Hamiltonian actions.
  • Binary codes and matroids: When all action values equal θ, an X-program can be represented by a binary matrix whose rows encode Hamiltonian terms.The output distribution is connected to binary codes and matroids derived from this matrix.
  • IQP oracle: An IQP oracle efficiently returns a sample bitstring from the probability distribution generated by an explicitly described X-program.BPPIQP augments randomized polynomial-time classical computation with this sampling capability.
  • Directional bias: Theorem 1 expresses constant-action bias through the weight enumerator polynomial of the associated n_s-point matroid and binary code.This connects output statistics of IQP programs to code-theoretic structure.
  • Directional bias: For a direction s, directional bias depends only on θ and the matroid formed by rows of P that are not orthogonal to s.The bias is the probability that an output sample is orthogonal to s, and it is invariant under the choice of matrix representation.
  • Entropy and trivial cases: At an odd multiple of π/2, the returned sample is fixed and collision entropy is zero; at an odd multiple of π/4, the distribution is classically simulable to full precision.The π/4 case need not have zero collision entropy.

3 Interactive protocol

The section develops a two-party protocol in which a classical verifier challenges a supposedly quantum prover to demonstrate access to an IQP oracle using only classical messages. The protocol hides a causal matroid inside a larger published matroid and tests whether returned samples exhibit the expected secret-direction bias.

  • Protocol roles and flow: The game combines a code or matroid construction, an IQP sampling architecture, and a hypothesis test for verifying Bob’s attempt.The paper omits precise hypothesis-test details but provides source code separately.
  • Protocol roles and flow: Alice publishes an obfuscated matroid while Bob interprets it as an X-program, samples its IQP distribution, and returns the samples for testing.Alice hides the causal matroid using secret random data; Bob runs the published matrix with θ = π/8.
  • Verification: ∼200 qubits are suggested for a protocol that could convince a skeptic of some computational quantum effect, because classical simulation of the interactive transcript is expected to be infeasible.This claim assumes the relevant classical-separation and hidden-matroid-hardness conjectures.
  • Verification: Alice tests whether Bob’s samples are consistent with independent samples from the X-program distribution by checking their bias relative to her secret vector.She can compute the expected orthogonality probability from the code’s weight-enumerator polynomial and filters duplicate or null samples before testing.
  • Significance: The protocol is intended to validate early quantum architectures, especially systems with limited long-term coherence and shallow-depth computation.Its significance is compared with Bell-violation experiments for quantum communication, while its implementation still requires physically challenging long-range interactions.
  • Scope: The testing concept supplies proof data rather than unknown computational data or an NP-membership witness, leaving more computation-like applications open.The paper identifies finding a decision language specifically achievable by BPPIQP as an open problem.

3.3 Recommended construction method

The recommended construction uses quadratic residue codes embedded as hidden submatroids within larger binary matroids. The resulting protocol is conjectured to separate quantum and best-known classical sampling biases while making the hidden structure computationally difficult to recover.

  • Code choice: Quadratic residue codes are recommended for Alice’s causal code because they produce a non-negligible gap between quantum and best-known classical bias expectations.The construction uses a prime q with q + 1 divisible by eight; the code has length q and rank (q + 1)/2.
  • Bias gap: 85.4% quantum bias versus 75% classical bias is predicted for samples orthogonal to the hidden vector when θ = π/8.Alice’s test measures this characteristic after removing duplicate and null samples.
  • Security boundary: Exponential classical resources would let Bob simulate an IQP oracle and obtain approximately 85.4% bias, so the proposed security is computational rather than unconditional.The paper also conjectures that Bob cannot pragmatically boost the classical signal without feedback from Alice or exponential resources.
  • Obfuscation: The construction obfuscates a public quadratic-residue-code matroid by embedding it in a larger, effectively random matroid and hiding the removable rows.Appending redundant columns and random rows, followed by column reduction, preserves the relevant matroid structure while obscuring the embedded code.
  • Computational assumption: The language of matroids containing a sufficiently large quadratic-residue-code submatroid by point deletion is conjectured NP-complete.The hidden-submatroid problem is presented as apparently independent of conjectures about classical hardness of IQP simulation.

3.4 Challenge

The authors propose randomized IQP-capability challenges with large-entropy distributions that are easy to validate but conjectured infeasible to forge classically. They also publish a concrete q = 487 challenge and its checking software.

  • 3.4 Challenge: q ∼500 challenges are conjectured to produce large-entropy distributions that are easy to validate but infeasible to forge without IQP capability or the secret s vector.The authors propose these challenges as targets for early quantum architectures because they appear to require little temporal structure and relatively few qubits.
  • 3.4 Challenge: A public q = 487 challenge offers a $25 incentive and provides the challenge-generation and candidate-checking source code, excluding the secret randomization seed.

4 Heuristics

The paper next examines why the proposed problem class may be classically intractable and reports its failure to identify a decision language establishing IQP's worth.

  • 4 Heuristics: The section addresses classical intractability heuristics and the authors’ failure to find a decision language for proving the worth of IQP.

4.1 Hardness of strong simulation

The paper supports strong-simulation hardness by connecting IQP probabilities to binary-code weight enumerators. Accurate probability evaluation can recover arbitrary weight-enumerator coefficients, yielding PGapP-hardness.

  • 4.1 Hardness of strong simulation: Strongly simulating the generic probability distributions arising in this paradigm is PP-complete.
  • 4.1 Hardness of strong simulation: Determining P(X = 0) for arbitrary matroids to exponential precision is PGapP-hard.
  • 4.1 Hardness of strong simulation: The relevant probability is a function of the weight-enumerator polynomial of the binary linear code KerL(P).
  • 4.1 Hardness of strong simulation: Varying θ over (0, π/2) and accurately evaluating P(X = 0) enables recovery of integral weight-enumerator coefficients, whose arbitrary recovery is PGapP-hard.

4.2 Background

The background contrasts IQP with restricted circuits that are classically simulable and with prior shallow or temporally unstructured quantum algorithms. It emphasizes that Simon’s oracle does not fit the BPPIQP framework because it does not commute with the Hadamard transform.

  • 4.2 Background: Known classically simulable circuits often rely on constrained circuit topology, whereas the paper’s Z-network imposes no particular circuit topology.
  • 4.2 Background: Shor’s algorithm has been implemented in constant timesteps on a Graph State processor, but prior constructions give no reason to expect a constant below roughly 100.
  • 4.2 Background: Simon’s algorithm is not an example within BPPIQP because its oracle implements a unitary that does not commute with the Hadamard transform.

4.3 Conjectures, implicit and explicit

The paper presents conjectures about the classical hardness of IQP distributions and the collision entropy needed for its interactive games. These conjectures support, but do not prove, the proposed separation from efficient classical simulation.

  • Random X-programs are conjectured to produce distributions exponentially close to flat random, while non-random instances lack an evident efficient classical sampler.
  • Conjecture 2 posits that no classical polynomial-time machine can gain a non-negligible advantage in deciding whether random X-program distributions are exponentially close to uniform.
  • The proposed protocol relies on the plausibility that classical polynomial-time devices misestimate some event probability for almost any X-program of interest.
  • The paper conjectures that expected collision entropy for width-n X-programs with θ = π/8 scales as n − O(1), supporting the protocol's sampling test.

4.4 Classical approximations

The paper constructs a classically simulable distribution from second-order differential information and relates it to IQP output correlations through binary-matroid structure. The resulting theorem identifies when a hidden direction can be recovered classically.

  • Directional derivatives: For θ = π/8, the analysis uses second-order discrete derivatives, while θ = π/2^d+1 would require dth-order derivatives.
  • Directional derivatives: The second derivatives are linear functions of the input bits over Z/16Z, regardless of the chosen directions.
  • Directional derivatives: A hidden s satisfying P(X · s^T = 0) = 1 forces f_s(a) ≡ 0 (mod 16) for every a, yielding a Simon-like hidden-shift structure.
  • Classical sampling: The classical random variable Y is generated by uniformly choosing d and e, then summing rows of P non-orthogonal to either direction.
  • Classical sampling: The bias of Y in direction s is determined by the matroid P_s, and Theorem 2 proves P(X · s^T = 0) = 1 implies P(Y · s^T = 0) = 1.
  • Classical sampling: The converse appears to fail only in trivial cases where P_s has repeated rows, corresponding to circuits of length 2.
  • Classical sampling: The authors describe Y as their best classical approximation, capturing local information while excluding non-local matroid information available to the quantum distribution.

4.5 Future work

The paper identifies further questions about matroid invariants and the communication needed for nontrivial IQP tasks.

  • The authors propose studying matroid and weighted-matroid invariants as natural objects for IQP computation and possible sources of genuinely quantum capabilities.
  • Because Theorem 2 correlates the quantum and classical variables, nontrivial tasks without communication or multiple parties remain an open problem.

5 Architectures

The paper compares X-programs with Z-network and Graph-program architectures, showing efficient reductions while exposing different trade-offs in gatespan, depth, and qubit count.

  • Z-networks: Z-networks use CNOT gates and single-qubit Z rotations; their restricted group supports the probability distributions studied for IQP.
  • Z-networks: The restricted Z-network group does not apparently contain classical-computation dynamics efficiently, limiting its computational scope.
  • Reductions between Z-networks and X-programs: A Z-network can efficiently simulate any X-program by using Hadamard-basis input and output, CNOT gates, and one exp(iθZ) gate per program row.
  • Reductions between Z-networks and X-programs: Conversely, an X-program efficiently simulates Z-networks restricted to Hadamard input, CNOTs, X gates, exp(iθZ) gates, and Hadamard-basis output.
  • Reductions between Z-networks and X-programs: These reductions place simple Z-networks relative to X-programs as the full SU(2^n) group relates to unrestricted quantum algorithms.
  • Graph-programs: Graph-programs build a graph state and perform fixed, non-adaptive measurements simultaneously, giving them depth 1 after graph-state preparation.
  • Architecture trade-offs: X-programs minimize temporal structure but may require gatespan up to n; Z-networks use gatespan 2 but likely quadratic depth, while Graph-programs use more qubits with better depth.
  • Graph-programs and X-programs: A Graph-program can efficiently simulate an X-program by adding one ancilla per program element and classically post-processing the measurement outcomes.

Appendix

The appendix proves theorem 1 and derives intermediate expressions by changing basis, applying Fourier decomposition, and substituting variables in the correct basis.

  • The proof treats rows of the binary matrix P as the program elements of an X-program.
  • The appendix derives line (8) from line (1) when θ is constant.
  • A basis change replaces Pauli X operators with Pauli Z operators, although the resulting transformations are notationally untidy.
  • The resulting expressions relate P(j = 2(ns−2·wt(c)) | c ∼ Cs) to cos(2θ(ns−2w))·P(w = wt(c) | c ∼ Cs).
  • The derivation uses the Fourier decomposition of a known-real periodic function and substitutes c = Ps·aT and w = (2ns−j)/4 in the appropriate basis.
Loading 0809.0847v3…