Quantum technologies aim to leverage quantum resources for computational speedups. Several tasks have been proposed to demonstrate this advantage, including Boson Sampling and random quantum circuits. However, practical demonstrations are challenging due to difficulties in combining theoretical and experimental elements. Existing demonstrations often involve tasks lacking established classical algorithms, hindering benchmarking. Furthermore, verification is typically limited to narrow parameter ranges. This work focuses on demonstrating quantum advantage in an interactive setting for verifying NP-complete problems. The task involves an untrusted prover (Merlin) providing limited information to a verifier (Arthur) to check for a solution's existence, not the solution itself. The proposed approach uses simple quantum hardware, inherently verifiable yes/no answers, and benchmarking based on the widely accepted assumption that NP-complete problems lack subexponential algorithms. Unlike previous tasks, this approach has potential real-world applications, such as in server-client quantum computing, authentication, ethical behavior enforcement, and blockchain technologies.

The paper reviews prior work on demonstrating quantum computational advantage, highlighting Boson Sampling and random quantum circuits as examples. It discusses the challenges of benchmarking against classical methods due to the lack of well-established classical algorithms for many proposed quantum tasks. The difficulty in verifying the quantum advantage across a wide range of parameters and the lack of demonstrations for useful tasks are also addressed. The paper then examines the use of quantum protocols for verification in an interactive proof setting, referencing the concept of Quantum Merlin Arthur (QMA) problems and related research. It notes that QMA problems can provide more efficient verification of NP-complete problems than classical methods. The previous theoretical work on implementing quantum verification protocols with linear optics is also reviewed, acknowledging the limitations of practical implementation due to the large number of elements required.

The researchers focused on the 2-out-of-4 SAT problem, a reduction of the 3-SAT problem. They assume the instance is balanced (each variable appears in the same number of clauses) and probabilistically checkable (either satisfiable or a constant fraction of clauses are unsatisfiable). The quantum protocol involves Merlin (prover) sending a quantum proof to Arthur (verifier) encoded in a sequence of unentangled coherent states. The encoding uses displacement operators applied to the vacuum state, creating a coherent state with mean photon number μN, where N is the number of variables and μ is the mean photon number per pulse. Arthur verifies the proof using the Sampling Matching (SM) scheme. This involves interfering Merlin's coherent states with a sequence of uniform coherent pulses generated by Arthur in an interferometer. Clicks in two single-photon detectors (D0 and D1) are observed. Arthur assigns values to variables based on detector clicks (0 for D0, 1 for D1, random for double clicks, unassigned for no clicks). He then checks satisfiability of clauses for which all four variables have assigned values. In the case of honest Merlin (satisfiable instance), the completeness of the protocol is analyzed by considering the probability that Arthur obtains the values of all four variables in every clause. This probability is analyzed using the fact that the pulses are unentangled and that the probability of detecting a photon in each pulse is independent of the others. In the case of dishonest Merlin, the soundness of the protocol is determined by analyzing the probability that Arthur accepts a proof when no satisfying assignment exists. This probability is bounded by considering the minimum probability of Arthur obtaining a value for any variable, irrespective of Merlin's strategy. The paper then extends the analysis to include practical imperfections, considering imperfect visibility and dark counts in the detectors. Equations are developed to calculate the probability of correct and incorrect detections, and a threshold is determined to account for experimental errors. The methodology details how the researchers account for practical imperfections, such as imperfect visibility and detector dark counts. They modify the assignment strategy to handle double clicks and define a threshold for accepting/rejecting a proof based on the fraction of satisfied clauses, using Chernoff bounds to guarantee a sufficient gap between completeness and soundness. They also address a scenario where Merlin might send states with an incorrect photon number, either assuming honest photon number or considering how Arthur could check. Losses in the system are considered negligible due to a pre-calibration step. The experiment uses a continuous-wave laser, amplitude modulator, balanced beam splitters, phase modulators, and InGaAs detectors. The experimental procedure involves calibrating the phase shift and equalizing pulse power, measuring visibility, and then running the verification test with randomly generated satisfying assignments.

The experimental setup successfully demonstrated the quantum verification protocol. The experiment achieved high completeness (C > 0.9) and low soundness (S < 0.6) for different instance sizes (N) ranging from 5000 to 14000. The experimental data shows that the quantum verification time is linear in N, as predicted theoretically. The number of bits of information obtained by Arthur (number of clicks) is significantly smaller than N, satisfying the criteria for quantum advantage. The difference between N and the number of bits Arthur obtained (N - Sclk) was kept greater than 1000, making the classical verification practically infeasible, even when considering highly optimized SAT solvers. The results demonstrate a clear gap between quantum and classical verification times, with the quantum verification being significantly faster for sufficiently large problem instances. The analysis of the experimental data considers the visibility, mean photon number per pulse, and number of single and double clicks in the detectors. The gap between completeness and soundness (C-S) is shown to increase with increasing N, further supporting the claim of quantum advantage. Table 1 provides experimental data for various N values, highlighting the increasing number of missing bits (information Arthur lacks) with increasing N. The experimental data matches well with the theoretical analysis, validating the protocol's effectiveness. Figure 4 visually depicts the comparison between experimental and simulated data. The researchers carefully calibrated their experimental setup, accounting for the visibility of the interferometer and addressing potential error sources like detector dark counts. By comparing completeness and soundness, they demonstrate a clear quantum advantage for verifying NP-complete problems. This advantage is further enhanced by the limited information leakage to the verifier.

The experimental results validate the theoretical predictions and demonstrate a clear quantum advantage in the proposed verification task. The simplicity of the linear optical setup, combined with the Sampling Matching technique, highlights the potential of linear optics for computational tasks. The work suggests that the efficient verification of NP-complete problems with limited information leakage represents a step toward practical quantum applications. The authors propose potential future applications, such as in server-client quantum computing and quantum cryptography. The use of unentangled coherent states makes the experimental setup relatively straightforward, contributing to the feasibility of the demonstration. However, limitations of the experimental setup (such as visibility) and assumptions made in the theoretical analysis (e.g., unentangled states, correct mean photon number for dishonest Merlin) should be noted. The demonstrated quantum advantage is context-specific. Nevertheless, this is a significant step towards proving quantum advantages for useful tasks.

This research provides the first experimental demonstration of quantum advantage for verifying NP-complete problems with bounded information. The study utilizes a simple linear optical implementation of the Sampling Matching scheme, highlighting the potential of linear optics for computational tasks. While the demonstrated advantage is context-specific, it offers a stepping stone towards practical quantum applications, such as server-client quantum computing and cryptographic protocols. Future work could investigate further applications and explore ways to relax some of the current assumptions.

The quantum advantage demonstrated is specific to the chosen interactive proof system and assumptions made about the prover's behavior (unentangled states). The experimental demonstration involves a specific type of NP-complete problem (2-out-of-4 SAT) and may not generalize directly to all NP-complete problems. Imperfect visibility and detector dark counts in the experimental setup could introduce errors and potentially limit the generality of the results. The assumption of a balanced and probabilistically checkable 2-out-of-4 SAT instance simplifies the analysis but might not always hold true in real-world scenarios. The authors also point out that achieving a higher visibility and improving the control of the experimental apparatus would lead to a larger number of problem instances where the quantum advantage could be experimentally demonstrated.