Experimental demonstration of quantum advantage for NP verification with limited information

The study investigates whether quantum resources can provide a practical computational advantage in verifying NP-complete problems within an interactive prover-verifier framework, under limited information leakage about the proof. The context arises from previous quantum advantage proposals (e.g., Boson Sampling, IQP, random circuits) whose benchmarking and verification pose challenges. The authors target a task with a verifiable YES/NO outcome: verifying satisfiability of balanced, probabilistically checkable 2-out-of-4 SAT instances using limited information sent by an untrusted prover (Merlin) to a verifier (Arthur). They aim to demonstrate that, for fixed (small) proof size, a quantum protocol can verify efficiently (time linear in N), whereas classical verification with the same amount of revealed information would require exponential time in the remaining unknown variables, assuming NP-complete problems lack sub-exponential-time algorithms. The work’s importance lies in providing an experimentally accessible, inherently verifiable task with potential relevance to applications like server-client quantum computing and authentication, while highlighting that the advantage is in an interactive setting and concerns verification with bounded information, not solving NP-complete problems outright.

The paper reviews prior quantum advantage candidates: Boson Sampling and its small-scale implementations; sparse commuting circuits (IQP) and random quantum circuits culminating in Google’s Sycamore demonstration. It discusses the difficulty of benchmarking these tasks due to immature classical baselines, unclear intermediate-size scaling under noise, and limited verification windows. It recalls complexity-theoretic underpinnings (polynomial hierarchy assumptions) and the need for useful tasks. In interactive proof complexity, Quantum Merlin-Arthur (QMA) systems allow quantum-encoded proofs with completeness/soundness guarantees. Aaronson et al. showed that unentangled quantum proofs can enable more efficient verification of NP-complete problems. Prior linear-optics proposals with single photons were theoretically possible but experimentally impractical due to resource demands. The authors leverage coherent-state mappings and the Sampling Matching problem from communication complexity as a practical alternative, building on coherent-state protocols that have shown quantum advantages in communication tasks and security.

Protocol and theory: The NP-complete problem is reduced to a balanced, probabilistically checkable 2-out-of-4 SAT instance on N boolean variables, where each variable appears a constant number of times, and either the formula is satisfiable or any assignment violates at least a constant δ>0 fraction of clauses. The prover (Merlin) sends an unentangled quantum proof; the verifier (Arthur) performs a single interferometric test based on the Sampling Matching (SM) scheme. - Quantum proof encoding (coherent-state mapping): For an assignment x∈{0,1}^N, Merlin prepares a sequence of N coherent states with phases encoding x: |α_x⟩=⊗_{k=1}^N |(−1)^{x_k}α⟩_k, with mean photon number per pulse μ=|α|^2 and total μN. The protocol targets |α|^2 = O(N^{-1/4}), so Arthur’s total information scales as O(N^{3/4}). The unentanglement promise across pulses is essential. - Verification test (Sampling Matching-based interferometry): Arthur generates his own local sequence of N coherent pulses |α⟩ with the same mean photon number. Each time-bin k, Merlin’s pulse and Arthur’s pulse interfere on a balanced beam splitter. The two output ports are detected by single-photon threshold detectors D0 and D1. Ideally, only one detector has non-zero click probability depending on x_k, enabling Arthur to assign variable values: D0→0, D1→1; no click→unassigned. In practice, double clicks can occur; Arthur assigns a random bit in that case to avoid exploitable bias. - Theoretical detection probabilities: With ideal visibility, the click probabilities per time-bin depend on interference (Eq. (4)). With imperfect visibility v and negligible dark counts, correct, wrong, and double-click probabilities are given by P_c=(1−e^{−2v|α|^2})e^{−2(1−v)|α|^2}, P_w=(1−e^{−2(1−v)|α|^2})e^{−2v|α|^2}, and P_dc=(1−e^{−2v|α|^2})(1−e^{−2(1−v)|α|^2}). The average number of clicks is P·N with P=P_c+P_w+P_dc. Losses are calibrated and compensated by scaling pulse amplitudes by 1/η during a pre-calibration phase. - Completeness and soundness analysis: Completeness (YES instance) is limited only by failure to measure all four variables in any clause; with independent per-bin click probability p≥1−e^{−2|α|^2}, a given clause is fully measured with probability ≥p^4. With O(N) clauses, choosing |α|^2=O(N^{−1/4}) makes completeness near 1. Soundness (NO instance): Since any assignment leaves ≥δ fraction of clauses unsatisfied, and Arthur’s clicks occur with probability at least p_a≥1−e^{−|α|^2} due to his own pulses, the chance of detecting an unsatisfied clause scales as δ·p^4, so the probability of missing all unsatisfied clauses decays exponentially in N for appropriate |α|^2. In the presence of imperfections, the expected fraction of satisfied measured clauses in YES and NO cases are computed using P_Y (Eq. (8)) and an upper bound P_N (Eq. (9)), enabling a threshold T=(T_c+T_s)/2 and Chernoff bounds for completeness and soundness (Eqs. (10)-(11)). - Information leakage and classical baseline: Arthur’s information is upper bounded by the number of clicks, O(N(1−e^{−2|α|^2}))=O(N^{3/4}) for |α|^2=O(N^{−1/4}). Under the assumption that classical algorithms for 2-out-of-4 SAT require time ~2^{γN} and that revealing t bits reduces the residual hardness to ~2^{γ(N−t)}, classical verification with the same limited information remains exponentially hard. The experiment targets N−(number of single clicks) ≥ 1000 to render classical verification infeasible. Experimental setup and procedure: A CW laser at 1560 nm with amplitude modulation generates 10 ns pulses at 50 kHz. A 1/99 tap monitors power; pulses are attenuated, split by a balanced BS to Merlin and Arthur paths. Merlin encodes phases via a phase modulator (V_π calibrated); Arthur and Merlin adjust attenuators to equalize powers before interference on the output BS. Detection uses two InGaAs APD single-photon detectors (IDQuantique). Data acquisition is via a National Instruments card; software performs post-processing. - Calibration: Determine interferometer visibility v and total efficiency η (η_channel≈38%, η_det≈25%); visibility measured per run (nominal v≈0.93). Dark count probability P_dark≈10^{-3} is negligible for chosen μ and v. Parameters used: μ≈1.31, v≈0.93, δ=0.15 across runs, with actual visibilities recorded. No active phase feedback was needed due to slow drift relative to run time. - Protocol execution: For several N (5000–14000), Merlin sends a uniformly random satisfying assignment encoded in phases. Arthur records total clicks, single clicks, and double clicks. Variable assignment: single-click D0→0, D1→1; double click→random; no click→unassigned. Using measured P_c, P_w, P_dc (from counts/N), Arthur computes expected satisfied clauses for YES and NO via Eqs. (8),(9), applies threshold T, and infers acceptance (completeness). Theoretical soundness is computed from the same parameters. Information leakage is estimated by the number of measured bits (single clicks). Runtime: quantum acquisition sub-second; classical post-processing a few seconds; calibration a couple of minutes per run.

- Demonstrated an efficient quantum verification protocol for NP-complete 2-out-of-4 SAT in an interactive setting using coherent states and linear optics, with verification time O(N). - Parameter regime enabling advantage: theoretical analysis (N=10,000; v=0.91; δ=0.15) shows a region of mean photon number μ=|α|^2 where completeness C>0.9 and soundness S<0.6 simultaneously. - Experimental parameters: nominal μ≈1.31 photons/pulse, visibility per run v≈0.87–0.95; dark counts ≈10^{-3} negligible; N ranging from 5000 to 14,000. - Completeness: For N≥6000, the computed number of satisfied clauses substantially exceeded the threshold T, indicating acceptance with high probability. Examples (from Table 1): • N=6000: Threshold T=2717; Satisfied clauses=3231; Single clicks=4834; Correct single clicks=4741; Double clicks=719; Missing bits=1166. • N=10,000: T=4111; Satisfied=5082; Single clicks=8045; Correct single clicks=7929; Double clicks=947; Missing bits=1955. • N=14,000: T=6801; Satisfied=7437; Single clicks=11135; Correct single clicks=10950; Double clicks=1807; Missing bits=2865. - The only tested point without advantage was N=5000 due to lower visibility (v=0.87), yielding Satisfied=2227 vs T=2254. - Soundness: For the same parameters, theoretical upper bounds show soundness well below 0.6 and often close to 0 due to large T_c−T_s, with Chernoff bounds ensuring exponentially small error probabilities. - Information leakage: The number of learned bits (single clicks) scales as O(N^{3/4}); experiments ensured N − (single clicks) > 1000 for larger N, making equivalent classical verification computationally infeasible under standard NP assumptions. - Practical performance: Quantum data acquisition per run took <1 s; classical post-processing a few seconds; calibration on the order of minutes, demonstrating an end-to-end feasible procedure.

The findings confirm that, in an interactive proof setting with bounded information leakage, a simple linear-optical system using coherent states can efficiently verify NP-complete instances, achieving a computational advantage over classical verification constrained to the same proof-size limit. The Sampling Matching-based interferometric test ensures that Arthur obtains variable values with probabilities independent of Merlin’s strategy, preventing Merlin from biasing which variables are measured and enabling uniform clause coverage. The completeness-soundness gap persists under realistic imperfections (finite visibility and detector characteristics) by adopting a threshold on the fraction of satisfied measured clauses and using Chernoff bounds. The work demonstrates a practically implementable route to quantum advantage tailored to a verifiable, decision-type task, with potential implications for near-term quantum cloud scenarios where a client can verify a server’s computation without receiving full information, and for limited-knowledge proof systems relevant to authentication or blockchain-like applications. It emphasizes that the advantage pertains to verification with fixed, limited proof size and not to solving NP-complete problems outright.

This work provides the first experimental demonstration of a quantum computational advantage for verifying NP-complete problems in an interactive prover-verifier setting with limited information. By combining coherent-state encodings with a Sampling Matching-based interferometric test, the authors achieve linear-time verification with high completeness and low soundness for practically sized instances (N up to 14,000) using standard photonic components. The approach highlights linear optics and coherent states as promising tools for near-term, verifiable quantum computational tasks. Future directions include removing simplifying experimental assumptions (e.g., enforcing correct mean photon number without trust), improving visibility and stabilization for larger N and tighter bounds, implementing full PCP-sampled balanced instances, extending to broader classes of NP or QMA verification tasks, and exploring concrete applications in quantum cloud verification and secure, limited-knowledge proof systems.

- The advantage is shown in an interactive setting with a single message and bounded information, not in the standard model of standalone computation; it does not solve NP-complete problems. - The protocol relies on the unentanglement promise across the proof states; entangled proofs could invalidate the efficiency or security assumptions. - Experimental analysis of soundness is theoretical; experiments primarily assess completeness using randomly generated satisfying assignments rather than full sampled PCP instances. - A simplifying assumption for experimental analysis considers a dishonest Merlin that uses the prescribed mean photon number; fully general cheating strategies (with arbitrary photon numbers) require stricter visibility and conditions not met in the current setup. - Practical imperfections (finite visibility) affected performance; at N=5000 with v=0.87, the advantage was not observed. No active phase stabilization was used (not needed due to slow drift), but tighter control would benefit scalability. - Losses are handled via calibration and power adjustment; while acceptable here, real-world deployment may impose additional constraints. - The experimental inputs were uniformly random satisfying assignments rather than instances produced via an explicit reduction pipeline sampling balanced PCP instances, which would more closely emulate the full theoretical setting.