PaperlayerView exact revision on arXiv

Source-linked AI summary

Forging quantum data: classically defeating an IQP-based quantum test

Gregory D. Kahanamoku-Meyer

arXiv:1912.05547v3quant-phcs.CR

TL;DR

The open question is whether a classical prover can generate samples passing the IQP protocol’s orthogonality check without reproducing the quantum output distribution. The paper constructs a classical algorithm that extracts the hidden secret vector by solving linear constraints derived from the X-program. The algorithm recovers the secret vector with probability 1/2 per iteration, is efficient in practice, and the extracted key was confirmed as the correct key.

  • Problem

    The open question is whether a classical prover can generate samples passing the IQP protocol’s orthogonality check without reproducing the quantum output distribution.

    Source: §1 · p. 1

  • Method

    The paper constructs a classical algorithm that extracts the hidden secret vector by solving linear constraints derived from the X-program.

    Source: §1 · p. 2, §3.1 · p. 4

  • Results

    The algorithm recovers the secret vector with probability 1/2 per iteration, is efficient in practice, and the extracted key was confirmed as the correct key.

    Source: §1 · p. 2, §4 · p. 7

  • Takeaways & Limitations

    The original IQP protocol is no longer effective as a test of quantum computational power in its original form.

    Source: §4 · p. 7

    The analysis does not rigorously establish the typical rank of the generated matrix, leaving the scaling claim partly empirical.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

Recently, quantum computing experiments have for the first time exceeded the capability of classical computers to perform certain computations -- a milestone termed "quantum computational advantage." However, verifying the output of the quantum device in these experiments required extremely large classical computations. An exciting next step for demonstrating quantum capability would be to implement tests of quantum computational advantage with efficient classical verification, such that larger system sizes can be tested and verified. One of the first proposals for an efficiently-verifiable test of quantumness consists of hiding a secret classical bitstring inside a circuit of the class IQP, in such a way that samples from the circuit's output distribution are correlated with the secret (arXiv:0809.0847). The classical hardness of this protocol has been supported by evidence that directly simulating IQP circuits is hard, but the security of the protocol against other (non-simulating) classical attacks has remained an open question. In this work we demonstrate that the protocol is not secure against classical forgery. We describe a classical algorithm that can not only convince the verifier that the (classical) prover is quantum, but can in fact can extract the secret key underlying a given protocol instance. Furthermore, we show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits. Finally, we provide an implementation of the algorithm, and give the secret vector underlying the "$25 challenge" posted online by the authors of the original paper.

1 Introduction

The paper addresses whether a classical prover can pass an efficiently verifiable IQP-based quantum test without simulating the quantum distribution. It answers yes by extracting the hidden secret vector, enabling forgery and undermining the protocol’s security.

1 Introduction

  • The work challenges a protocol whose classical security was motivated by the hardness of directly simulating IQP circuits.Hard simulation does not rule out non-simulating attacks that target the verifier’s checked property.Source: §1 · p. 1
  • The protocol checks whether output bitstrings are orthogonal to a secret vector rather than verifying that samples follow the correct distribution.This leaves open attacks that generate passing samples without reproducing the quantum circuit’s output distribution.Source: §1 · p. 1
  • The extraction algorithm is polynomial and fast in practice for X-programs with hundreds of qubits.Figure 1 summarizes runtime measurements, while the experiments successfully extracted every tested secret vector.Source: Figure 1 · p. 2, §1 · p. 2
  • The paper gives an explicit classical algorithm that extracts the secret vector and therefore generates samples passing the verifier’s test.A single iteration succeeds with probability 1/2, which can be increased arbitrarily close to 1 through repetition.Source: §1 · p. 2
  • The paper also reports the secret key for the original “$25 challenge” and confirms it with the challenge authors.The implementation and challenge result demonstrate the attack on a concrete published instance.Source: §1 · p. 2

2 Background

The IQP protocol hides a secret vector in a structured X-program so quantum samples are biased toward strings orthogonal to that vector. Its background combines code-based construction, scrambling, and a classical strategy that motivates the improved attack.

2 Background

  • The verifier requests samples and checks whether too large a fraction satisfies X · s = 0, exploiting a gap between quantum and classical success probabilities.The code structure and action determine the relevant probability expressions through expectations over codewords.Source: §2 · pp. 2–3
  • An X-program is a binary matrix whose rows specify products of Pauli X operators, with action θ controlling the Hamiltonian evolution.For this protocol, the action is θ = π/8.Source: §2 · p. 2
  • The protocol embeds a structured submatrix Ps inside a larger scrambled matrix while preserving the bias of measurement outcomes relative to secret vector s.Rows orthogonal to s do not affect Pr[X · s = 0], so the verifier attempts to hide Ps by appending and scrambling rows.Source: §2 · pp. 2–3
  • The construction uses a binary code with block length q ≡7 (mod 8), codeword weights in {−1, 0} (mod 4), and θ = π/8.Binary quadratic-residue codes are suggested because they have the required weight properties.Source: §2 · p. 3
  • The previously known classical strategy produces vectors orthogonal to s with probability 3/4.The proof uses codeword parity and the fact that the relevant codewords are orthogonal whenever at least one has even parity.Source: §2 · p. 3
  • The paper uses this classical strategy as the setup for an improved algorithm that defeats the protocol.The next section develops the improvement rather than merely simulating the IQP distribution.Source: §2 · p. 3

3 Algorithm

The paper gives a classical algorithm that extracts the secret vector from the protocol, succeeds with probability 1/2 per iteration, and is empirically efficient for protocol-generated X-programs. Its implementation exploits linear solving, repeated randomized construction, and bit-level parallelism.

3 Algorithm

  • The algorithm correlates vectors by fixing one random bitstring d, varying e, and solving Msi = 1 for candidate secret vectors.When Ps d has even parity, all generated vectors satisfy the required orthogonality relation; the candidate set is then checked for the doubly-even code property.Source: §3 · p. 4, §3.1 · p. 4
  • The construction adds m* to each generated vector so the linear system uses mi · s = 1, with m* formed from the sum of rows of P.The analysis establishes m* · s = 1 and the shifted vectors' inner products are zero with probability 1/2.Source: §3 · p. 4, §3.1 · p. 5

3.1 Analysis

  • A single iteration outputs the secret vector s with probability 1/2 for an X-program containing a unique suitable submatrix Ps.The proof shows that Ms = 1 with probability 1/2, after which the algorithm's check outputs s.Source: §3.1 · pp. 4–5
  • If multiple suitable submatrices exist, the algorithm can accumulate all corresponding vectors, although unintended extra submatrices are expected with probability at most 1/4^n.The theorem itself assumes a unique suitable submatrix.Source: §3.1 · p. 5
  • The runtime claim remains empirical because correlations among generated rows make the rank of M difficult to analyze rigorously.The candidate-set size is 2^(n−rank(M)), so low-rank matrices could otherwise obstruct the claimed scaling.Source: §3.1 · p. 5
  • For 1000 unique X-programs at each tested problem size, the average number of candidate vectors checked before finding secret vector s remained qualitatively constant with n and was only about 4, indicating efficient extraction.Source: §3.1 · pp. 4, 6, Figure 2 · p. 5

3.2 Implementation

  • The implementation accelerates vector operations by packing bits into 64-bit integers and using AVX SIMD instructions, removing one factor of n for problem sizes around 100.The implementation and figure-generation code are provided in Julia, with experiments run on one thread of an Intel 8268 Cascade Lake processor.Source: §3.2 · p. 6

4 Discussion

The discussion examines ways to modify the protocol against the attack, while emphasizing that provably hard verification may require more complex quantum circuits. It also reports recovery and confirmation of the secret key for the original "$25 challenge" and concludes that the protocol is ineffective as a quantum test in its original form.

Modifications to the protocol

  • Preventing the attack by removing the hidden submatrix’s special property conflicts with the same property’s role in creating the protocol’s sampling bias.The attack exploits codewords whose weights lie in {−1, 0} (mod 4), while that property produces samples biased toward x · s = 0.Source: §4 · p. 6
  • A second defense would need to stop the generated vectors from becoming linearly independent, but the required rank-n embedded code makes this difficult.Adding structure to the extra rows could also reveal more information about the secret vector.Source: §4 · p. 6

Protocols with provable hardness

  • Provably hard protocols based on trapdoor claw-free functions offer stronger security, but require larger and more complex quantum circuits.The paper identifies simplified provably secure protocols as an area for further research.Source: §4 · p. 6

The $25 challenge

  • The protocol’s original challenge offered $25 for samples passing the verifier’s check for a published matrix P.The recovered secret vector corresponds to that challenge instance.Source: §4 · pp. 6–7

Summary and outlook

  • The attack shows that the original protocol is no longer effective for testing quantum computational power.The authors stress that verification security must be established, not merely the hardness of simulating the quantum device.Source: §4 · pp. 6–7

Related papers

Loading 1912.05547v3…