HTML
-
An instance of SAT is formalized as the conjunction of a set of clauses ϕ = c1 ∧ c2... ∧ cj, each of which is the disjunction of a set of literals l1 ∨ l2... ∨ lm. A literal could be a variable xi or a negation of a variable ¬xi. In 3-SAT instances, each clause has exactly three literals. The quantum verification of 3-SAT corresponds to the complexity class Quantum Merlin-Arthur [QMA(K)], as the quantum analogue of NP36-38. In this scheme, K non-communicating, omniscient provers (called Merlins) send K unentangled quantum proofs to a skeptical, computationally bounded verifier Arthur to convince Arthur the instance is satisfiable (see Fig. 1a). Arthur checks the proof in his computing machines and decide whether to accept or reject the proof. Two properties are required in a QMA protocol: (ⅰ) Completeness: if the instance is satisfiable, there exist a proof such that Arthur accepts with at least some high probability c; (ⅱ) Soundness: if the instance is not satisfiable, for any proof Arthur accepts with at most some probability s.
Fig. 1 Quantum verification machine.
a The two-prover Quantum Merlin-Arthur protocol [QMA(2)]. On the basis of the given SAT instance, the two Merlins send unentangled, identical proof states to Arthur, who checks the proof on his quantum computer and makes an "accept" or "reject" decision. b The architecture of quantum circuit for the satisfiability and uniformity test. The design comprises proof encoding, tunable permutations and measurement on the modes. These operations are mainly based on tunable two-mode transformations u combined with mode splitting and routing. With the input of single photons, the circuit can verify the satisfiability of a set of clauses or the uniformity on random matchings. c Experimental setup for the satisfiability test and uniformity test. Merlins prepare single photons distributed in the polarization and path modes, encoding the assignment in the single-photon states as quantum witnesses. Arthur then applies permutations and interferences on these modes with linear optics. Note only states from one Merlin are required for the two tests. The output modes are detected by single-photon avalanche diodes (SPADs) and registered by a time tagger. BBO β-barium borate crystal, BD calcite beam displacer, P polarizer, IF interference filter, SMF single mode fibre, PBS polarizing beam-splitter.The protocol firstly reduces the 3-SAT instance to a 2-out-of-4 SAT instance where each clause contains four variables xi, xj, xk, xl and is satisfied if two of them are true, i.e., xi + xj + xk_xl = 2. In the verification, Merlins are supposed to send Arthur $K = O(\sqrt n)$ identical, unentangled quantum states28, each of the form
$$ |\psi \rangle = \frac{1}{{\sqrt n }}\mathop {\sum}\nolimits_{i = 1}^n {( - 1)^{x_i}|i\rangle } $$ (1) where $|i\rangle = \hat a_i^{\dagger} |0\rangle$ and $\hat a_i^{\dagger}$ is the creation operator on mode i. Here x1, x2, ..., xn ∈ {0, 1}n is an assignment of the n variables. A state of such form is called a proper state. The n-dimensional quantum state can be equivalently described by logn qubits revealing at most logn bits information by measurements on the state. To check whether the assignment x satisfies the clauses, Arthur can choose some clauses (i, j, k, l) at random and measure the K copies of |ψ〉 in a basis with a projection on |c〉 = (|i〉 + |j〉 + |k〉 + |l〉)/2 for each clause. For each copy Arthur will get a probability of observing the outcome |c〉
$$ p_c = |\langle c|\psi \rangle |^2 = [( - 1)^{x_i} + ( - 1)^{x_j} + ( - 1)^{x_k} + ( - 1)^{x_l}]^2/4n $$ Then Arthur rejects the proof if he gets the outcome |c〉 for at least one copy and accepts it otherwise. With this Satisfiability Test, Arthur will have pc = 0 if xi + xj + xk + xl = 2, and some constant nonzero probability otherwise. An issue is that Merlins may cheat Arthur by sending him improper state, for example concentrating the amplitude in a subset of the basis {|i〉} such that the Satisfiability Test passes even the instance is not satisfiable. To tackle this problem Arthur can perform Uniformity Test: he randomly chooses a matching M on the set {1, ..., n} such that the set is partitioned into n/2 groups of the form (i, j), then measures each copy of the state |ψ〉 in the basis with {|i〉 + |j〉, |i〉 − |j〉} for each (i, j) ∈ M. Only if the state is proper (i.e., the amplitudes are equal), one of the two outcomes will never occur. With the statistics on the outcomes, Arthur rejects the proof if two outcomes {|i〉 + |j〉, |i〉 − |j〉} both occur for a same (i, j) ∈ M. Here the K copies are used to obtain sufficient statistics on the outcomes to make a decision.
As the verification requires multiple copies of the state, another possible way for Merlins to cheat is to send different states rather than identical copies. For this reason, Arthur performs Symmetry Test: a swap test between two states, which accepts with certainty if the two states are identical and has a constant probability to reject when the two-state overlap is under a certain threshold. The QMA(K) protocol may be significantly reduced by simulating the K Merlins with a single Merlin who sends a product state of the K copies |ψ〉⊗K, yet in this case Arthur needs to guarantee the unentanglement among the K subsystems. To this end Arthur can ask for the proof state $|\psi \rangle ^{ \otimes K} \in {\Bbb C}_d^{ \otimes K}$ from another Merlin and conduct a Product Test32, which applies the swap test to each of the K pairs of corresponding subsystems of the two states. The proof will be accepted if all the swap tests pass and rejected otherwise. With the help of the product test, we can simulate the K-prover protocol with only two Merlins, which corresponds to the complexity result QMA(K) = QMA(2) for K ≥ 2 32.
Overall, Arthur performs one of the four aforementioned tests with constant probability (e.g., 1/4 each). As a consequence, we have an efficient quantum algorithm to verify SAT with perfect completeness and constant soundness, using two unentangled proofs of length $O(\sqrt n {{{\mathrm{log}}}}n)$ qubits (see Materials and methods for a summary of the protocol).
-
To realize the verification algorithm in photonic regime, we devise optical circuits for the four tests and experimentally implement the circuit in the case n = 6. The proofs from the two Merlins are unentangled photons generated by a parametric down-conversion process while the K copies of the state |ψ〉 correspond to photons generated sequentially at different time. In our experiment the K copies sent by a same Merlin are identical due to the fact that the apparatus to prepare the states is fixed within the duration of the experiment. For each copy we encode the n-dimensional quantum state in the polarization and path degrees of freedom of the photon. The optical modes {|1〉, |2〉, |3〉, |4〉, ..., |n〉} are mapped to {|h1〉, |v1〉, |h2〉, |v2〉, ..., |vn/2〉}, where |hj〉 (|vj〉) denotes the horizontal (vertical) polarization in path j. In the following we use |x1 x2 x3 x4 x5 x6〉 to represent a proper state given in Eq. (1) encoding the assignment x1 x2 x3 x4 x5 x6. When xi = 0 the phase on mode i is 0, whereas xi = 1 the phase is π.
Figure 1b depicts the circuit design for the satisfiability test and uniformity test. The circuit comprises a sequence of stages, each of which involves a set of two-mode configurable transformations u combined with mode splitting or routing (see Materials and methods for details). Starting from proof encoding, Merlin firstly splits the input single photon into an equal superposition over n modes and encodes the assignment x into the K copies of the state. Each state is then sent to successive tunable permutation modules, which select the modes corresponding to the chosen clause (i, j, k, l) or group the modes into a random matching M. Finally, the measurement and decision module performs either projection on the certain state |c〉 or two-mode interferences on the certain matching M. The two-mode transformations u are implemented by half-wave plates (see Fig. 1c), of which the optical axes can be set in different angles to perform different two-mode sub-operations such as Pauli-X, Pauli-Z and Hadamard gates
$$ X = \frac{1}{{\sqrt n }}\left({\begin{array}{*{20}{l}} 0 \hfill & 1 \hfill \\ 1 \hfill & 0 \hfill \end{array}} \right), Z = \frac{1}{{\sqrt n }}\left({\begin{array}{*{20}{l}} 1 \hfill & 0 \hfill \\ 0 \hfill & { - 1} \hfill \end{array}} \right), H = \frac{1}{{\sqrt {2n} }}\left({\begin{array}{*{20}{l}} 1 \hfill & 1 \hfill \\ 1 \hfill & { - 1} \hfill \end{array}} \right) $$ With appropriate configurations of these gates, the circuit can perform different permutations and interferences on the optical modes. The ability of the permutation stage is to sort the modes into groups (2 or 4 modes each, without regard to order). Configurations of the optical circuit are designed to realize the $\left({\begin{array}{*{20}{l}} 6 \hfill \\ 4 \hfill \end{array}} \right) = 15$ projections and the $\left({\begin{array}{*{20}{l}} 6 \hfill \\ 2 \hfill \end{array}} \right) \times \left({\begin{array}{*{20}{l}} 4 \hfill \\ 2 \hfill \end{array}} \right) \div 3! = 15$ matchings. The measurement outcome is read out by single-photon avalanche diodes and we register the measurement outcome for each copy of the proof state with a multi-channel time tagger. For a single trial of the test, a decision on the proof ("reject" or "accept") is made based on the detector pattern of K copies: for the satisfiability test, whether the detector corresponding to the projector |c〉〈c| clicks; for the uniformity test, whether the two detectors in a same group (i, j) both click.
-
Firstly we demonstrate the performance of the verifier in the satisfiability and uniformity tests. By changing the settings of the wave plates to prepare the 64 proper states and verify the 15 clauses, we measure the probabilities pc for all the 64 × 15 cases (Fig. 2a), which are consistent with the theoretical satisfiability of the clauses (Fig. 2b). The satisfying proofs manifest nearly zero outcome probabilities (0.28% in average), whereas all the unsatisfying proofs manifest significant outcome probabilities exceeding the probabilities of the satisfying cases by two orders of magnitude (larger than 13.47%). Regarding the uniformity test, we show the rejection probabilities when testing the 64 proper states for the 15 matchings with K = 3 in Fig. 2c. The results exhibit a high probability of 98.67% to accept in average. For the case that Merlins send improper states, we run the uniformity test for proof states of the form $|\psi _{{{{\mathrm{im}}}}}(\theta)\rangle = ({{{\mathrm{cos}}}}\theta, {{{\mathrm{sin}}}}\theta, {{{\mathrm{cos}}}}\theta, {{{\mathrm{sin}}}}\theta, {{{\mathrm{cos}}}}\theta, {{{\mathrm{sin}}}}\theta)/\sqrt 3$ with different numbers of copies K = 3, 4, 5, 6 (Fig. 2d). Here (α1, α2, α3, α4, α5, α6) denotes a state with complex amplitudes αi in mode |i〉, i.e., $\mathop {\sum}\nolimits_{i = 1}^n {\alpha _i|i\rangle }$. An increase in the rejection probability is observed with the transition from proper states to highly improper states, which fits the numerical simulations. On the other hand, higher rejection probabilities are obtained for improper states when increasing the number of copies K. In addition, we determine the average statistical fidelity ${{{\mathcal{F}}}}_c = \left({\sqrt {p_c^{{{{\mathrm{the}}}}}p_c^{{{{\mathrm{exp}}}}}} + \sqrt {\left({1 - p_c^{{{{\mathrm{the}}}}}} \right)\left({1 - p_c^{{{{\mathrm{exp}}}}}} \right)} } \right)^2$ between the theoretical and experimental projection probabilities ($p_c^{{{{\mathrm{the}}}}}$ and $p_c^{{{{\mathrm{exp}}}}}$) to be 0.9988 ± 0.0024 (see Fig. 2e), which justifies the excellent agreements between experimental results and theoretical calculations.
Fig. 2 Validation of the satisfiablity test and uniformity test.
a The experimentally measured projection probabilities pc when verifying the 15 clauses (rows) with the 64 proper states (columns). Here the proof states from left to right are |000000〉, |100000〉..., |111111〉, while the verified clauses from top to down are (1, 2, 3, 4), (1, 2, 3, 5)..., (3, 4, 5, 6). (i, j, k, l) denotes the clause xi + xj + xk + xl = 2. b The satisfiability of the 15 clauses for the 64 assignments. An assignment x may satisfies (white) or unsatisfies (blue) a certain clause. c The measured rejection probabilities of the uniformity test for the 64 proper states × 15 matchings when the number of copies K = 3. d The rejection probability$p_r^{{{{\mathrm{uni}}}}}$ of the uniformity test for improper states of the form$p_r^{{{{\mathrm{uni}}}}}$ . Here we take the results for the matching {(1, 2), (3, 4), (5, 6)} under different numbers of copies as an example. For each θ we run the test 5000 times and collect the measurement outcomes of 5000 × K photons to acquire the rejection probability$|\psi _{{{{\mathrm{im}}}}}(\theta)\rangle = ({{{\mathrm{cos}}}}\theta, {{{\mathrm{sin}}}}\theta, {{{\mathrm{cos}}}}\theta, {{{\mathrm{sin}}}}\theta, {{{\mathrm{cos}}}}\theta, {{{\mathrm{sin}}}}\theta)/\sqrt 3$ . The results given by numerical simulations are shown as solid lines. Error bars are uncertainties assuming Poisson count statistics. e The statistical fidelities$p_r^{{{{\mathrm{uni}}}}}$ between the theoretical probabilities${{{\mathcal{F}}}}_c = \left({\sqrt {p_c^{{{{\mathrm{the}}}}}p_c^{{{{\mathrm{exp}}}}}} + \sqrt {\left({1 - p_c^{{{{\mathrm{the}}}}}} \right)\left({1 - p_c^{{{{\mathrm{exp}}}}}} \right)} } \right)^2$ and experimental probabilities$p_c^{{{{\mathrm{the}}}}}$ for the 64 × 15 cases of the satisfiability test.$p_c^{{{{\mathrm{exp}}}}}$ To demonstrate the verification of specific instances, we concentrate on the instances including eight clauses, in which there are $\left({\begin{array}{*{20}{l}} {15} \hfill \\ 8 \hfill \end{array}} \right) = 6435$ instances. According to the satisfiability of the clauses (Fig. 2b), 90 instances are satisfiable (each with two solutions) and 6345 instances are unsatisfiable. Figure 3 visualizes the results of verifying a satisfiable instance ϕ1 (illustrated in Fig. 3a) and an unsatisfiable instance ϕ2 (illustrated in Fig. 3b). As Merlins aim to make Arthur accept the proof, for the satisfiable instance ϕ1 Merlins will honestly send the proof encoding one of the two satisfying assignments. In this case the proof states successfully pass both tests with high probabilities ($p_r^{{{{\mathrm{sat}}}}} = 0.64{{{\mathrm{\% }}}}$ and $p_r^{{{{\mathrm{uni}}}}} = 1.31{{{\mathrm{\% }}}}$, averaging over the two states), as shown in Fig. 3c.
Fig. 3 Experimental verification of SAT instances.
a The satisfiable instance ϕ1. b The unsatisfiable instance ϕ2. The shaded squares (green) illustrate which 8 of the 15 clauses are chosen in the instance. c The rejection probabilities of the satisfiability test ( , top) and uniformity test ($p_r^{{{{\mathrm{sat}}}}}$ , down) for different proof states. For the satisfiable instance ϕ1, Merlins will send proof states encoding the correct solution thus we show the results for the two satisfying proof states (red bars). For the unsatisfiable instance ϕ2, we test different cases consisting of sending the 64 proper states (blue bars), a deliberate cheating state |ψch1〉 in order to pass the satisfiability test (yellow bars), and improper states |ψim(θ)〉 (gray bars). The number of copies K = 3 is adopted in the verification and the rejection probabilities are obtained by repeating each test 5000 times.$p_r^{{{{\mathrm{uni}}}}}$ For the unsatisfiable instance ϕ2, we consider situations where Merlins send different types of states (Fig. 3c). Firstly we perform the two tests with all the 64 proper states. The verifier attains rejection probabilities $p_r^{{{{\mathrm{sat}}}}}$ larger than 11.50% and up to 95.72% in the satisfiability test although these proofs could probably pass the uniformity test ($p_r^{{{{\mathrm{uni}}}}} = 1.30{{{\mathrm{\% }}}}$ averaging over the 64 proper states). Secondly we realize cheating Merlins by sending deliberately designed improper states in order to pass the satisfiability test. As an example, we construct the state $|\psi _{{{{\mathrm{ch}}}}1}\rangle = (1, - 3, 1, 1, 1, 1)/\sqrt {14}$ (as well as $|\psi _{{{{\mathrm{ch}}}}2}\rangle = (- 3, 1, 1, 1, 1, 1)/\sqrt {14}$ for instances given in the Supplementary Information), for which the projection probability pc of verifying any of the eight clauses in ϕ2 theoretically equals zero. Consequently, |ψch1〉 reaches a rejection probability $p_r^{{{{\mathrm{sat}}}}} = 0.44{{{\mathrm{\% }}}}$ of the same order of magnitude as in the satisfiable case. Nevertheless, Arthur can detect the cheating with the help of the uniformity test, in which a rejection probability of 31.90% is obtained. This result justifies the necessity of the uniformity test. Finally the verification is also executed by sending just improper states |ψim(θ)〉 with θ = {−π/6, −π/12, 0, π/12, π/6}, which exhibit considerable rejection probabilities in both tests. We conclude from the results that for all the three cases, evident rejection probabilities are observed in at least one of the two tests. The typical realizations indicate close to perfect completeness and constant soundness and thereby experimentally achieve a clear completeness-soundness gap for the quantum verification (see Supplementary Information for more examples and results). Experimental imperfections, including the limited interference visibilities, phase fluctuations and errors in the operations, lead to deviations of the outcome probabilities from ideal ones for the satisfying proof states and thereby imperfect completeness for the protocol. In real-world applications of the QVM, of particular importance is the amplification of the completeness-soundness gap. For this reason we also demonstrate the amplification of the success probability for the instances ϕ1 and ϕ2, of which the protocol and results are given in the Supplementary Information.
The symmetry test and the product test require optical swap test39, which can be implemented with a multi-mode Hong–Ou–Mandel (HOM) interference (Fig. 4a)40. Our experiment uses a non-polarizing beam-splitter (NPBS) to perform the two-photon interferences on the six optical modes distributed in both polarization and path degrees of freedom. In the optical swap test, the probability of rejection is $p_r^{{{{\mathrm{swap}}}}} = (1 - |\langle \psi _1|\psi _2\rangle |^2)/2$, where |ψ1〉 and |ψ2〉 are the photonic states in the two input ports of the NPBS. We register all the $\left({\begin{array}{*{20}{l}} 6 \hfill \\ 2 \hfill \end{array}} \right) = 15$ coincidence channels, in which the six one-side channels (the two photons are detected in the same output port of the NPBS) correspond to the "accept" outcome and the nine two-side channels (the two photons are detected in different output ports of the NPBS) correspond to the "reject" outcome. We change the path difference between the two states with a delay line and observe the high-dimensional two-photon HOM interference. The HOM interference of identical proper states (Fig. 4b) manifests peaks for the "accept" outcomes and dips for the "reject" outcomes, resulting in a high acceptance probability of (97.48 ± 0.56)%. This result guarantees a high probability to accept in product test, as an experimental demonstration of the reduction from QMA(K) to QMA(2). To demonstrate the performance of the symmetry test, we apply the optical swap test to different combinations of states, as shown in Fig. 4c. On the basis of the outcome probabilities over the detector patterns, it can be concluded that considerable probabilities are obtained in the "reject" outcomes if the two states are not the same. The theoretical predictions also agree with the experimental results.
Fig. 4 The optical swap test.
a Experimental scheme. Two single photons are injected into the setup and prepared as two quantum proofs |ψ1〉 and |ψ2〉. The two states |ψ1〉 and |ψ2〉 are interfered at a non-polarizing beam-splitter (NPBS), and the interference results are read out by detectors. A time tagger registers single-shot events from all the twofold coincidence channels. The path difference between the two photons can be changed by a delay line to observe the interference. b Multi-dimensional Hong–Ou–Mandel (HOM) interference. Solid lines are curve fittings of the data to a Gaussian multiplied by a sinc function. A HOM interference dip (peak) is observed for the rejection (corrected acceptance) probabilities. Error bars are uncertainties assuming Poisson count statistics. c The results of the swap test for typical cases: the two states are proper and the same (the first panel); the two states are proper but not the same (the second and third panels), one of the state is proper and the another is improper (the fourth and fifth panels). Each panel shows the experimental (red and blue bars) and theoretical (yellow and gray bars) outcome probabilities on the 15 coincidence channels. The percentage labelled in each panel denotes the rejection probability of the swap test$p_r^{{{{\mathrm{swap}}}}}$
Quantum verification algorithm of the satisfiability problem
Photonic implementation of the quantum verification machine
Quantum verification of SAT instances with linear optics
-
The class QMA(K) consists of the set of decision problems having K unentangled polynomial-size quantum proofs that can be verified on a quantum computer in polynomial time. As the quantum analogue of the complexity class nondeterministic-polynomial-time (NP), QMA(K) has received extensive interests and many natural problems are proven to be in the class, such as N-representability49 in quantum chemistry. Formally, a language L is in QMA(K)c, s if there exists a polynomial-time quantum algorithm V such that, for all inputs x ∈ {0, 1}n:
(ⅰ) Completeness. If x ∈ L, there exists K witnesses with poly(n) qubits each, such that V outputs "accept" with probability at least c.
(ⅱ) Soundness. If x ∉ L, V outputs "accept" with probability at most s for all proof states.
Our quantum verification algorithm is a modified version of the recent proposals28, 32, 34. The protocol proceeds as follows.
Given a 2-out-of-4 SAT instance ϕ, each of the two Merlins sends to Arthur a quantum state in ${\Bbb C}_n^{ \otimes K}$ (with K subsystems). The two quantum states are denoted as |φ1〉 and |φ2〉 respectively. Arthur performs one of the following four tests, each with probability 1/4.
(1) Satisfiability Test. Arthur randomly chooses a block containing a set of clauses such that no variable appears more than once. Then Arthur measures each of the K subsystems from Merlin 1 in a basis corresponding to the clauses in the block. For each clause (i, j, k, l), Arthur performs the projection on |c〉 = (|i〉 + |j〉 + |k〉 + |l〉)/2. If the outcome |c〉 is obtained for at least one subsystem, reject. Otherwise, accept.
(2) Uniformity Test. Arthur randomly chooses a matching M on the set {1, 2, ..., n}, and measures each of the K subsystems from Merlin 1 in a basis containing $\{ (|i\rangle + |j\rangle)/\sqrt 2, (|i\rangle - |j\rangle)/\sqrt 2 \}$ for every edge (i, j) ∈ M. If for some edge (i, j), the two outcomes $(|i\rangle + |j\rangle)/\sqrt 2$ and $(|i\rangle - |j\rangle)/\sqrt 2$ both occur, reject. Otherwise, accept.
(3) Symmetry Test. Arthur chooses the subsystem 1 and another randomly chosen subsystem from Merlin 1, and performs a swap test on the two states. If the swap test passes, accept. Otherwise, reject.
(4) Product Test. Arthur performs swap test on each of the K pairs of corresponding subsystems of |ψ1〉 and |ψ2〉, and accepts if all of the swap tests pass. Otherwise, reject.
-
Frequency-doubled light pulses (~150 fs duration, 415 nm central wavelength) originating from a Ti: Sapphire laser (76 MHz repetition rate; Coherent Mira-HP) pump a beta barium borate (β-BBO) crystal phase-matched for type-II beamlike spontaneous parametric downconversion (SPDC) to produce degenerate photon pairs (830 nm central wavelength). The photon pairs are spectrally filtered by interference filters (IF) with 3 nm full-width at half-maximum and collected into single mode fibres (SMF). The pump power is set to ~150 mW to ensure a low probability of emitting two-photon pairs. By detecting one of the pair via a single-photon avalanche diode, we characterize the second order correlation function of heralded single photons to be g(2) (0) = 0.041 ± 0.008. A HOM interference visibility V = 0.969 ± 0.004 is observed, indicating a great indistinguishability between the two photons. The high indistinguishability guarantees a good performance of the optical swap test. See Supplementary Information for details about the g(2) (0) measurements and the HOM interference.
-
In the satisfiability test and uniformity test, Arthur merely needs to measure the quantum proof |ψ〉⊗K from one Merlin (Merlin 1 in the experiments), therefore the optical circuit shown in Fig. 1b is designed to perform local operations with the input of a single photon in each measurement. The single photons generated in the SPDC source are firstly delivered to polarization controllers and polarizers to prepare horizontally polarized states and then directed toward the optical circuit. The circuit is divided into three stages: (ⅰ) proof encoding; (ⅱ) a sequence of tunable permutations; (ⅲ) measurement and decision.
In Stage (ⅰ), firstly the input single photon passes the splitting module and evolves to an equal superposition on n/2 optical modes
$$ \hat a_1^{\dagger} |0\rangle \mapsto \sqrt {\frac{2}{n}} \left( {\mathop {\sum}\nolimits_{j = 1}^{n/2 - 1} {\hat a_{2j - 1}^{\dagger} + \hat a_n^{\dagger} } } \right)|0\rangle $$ (2) Here |0〉 denotes the vacuum state. This evolution is experimentally realized by a sequence of wave plates and calcite beam displacers. The following operation is a combination of n/2 two-mode transformations {uj(θj)}, which constitute an n-mode transformation
$$ U = \mathop { \oplus }\limits_{j = 1}^{n/2} u_j\left( {\theta _j} \right) $$ (3) Each two-mode transformation uj(θj) can be written as
$$ u_j(\theta _j) = \left( {\begin{array}{*{20}{l}} {{{{\mathrm{cos}}}}\theta _j} \hfill & {{{{\mathrm{sin}}}}\theta _j} \hfill \\ {{{{\mathrm{sin}}}}\theta _j} \hfill & { - {{{\mathrm{cos}}}}\theta _j} \hfill \end{array}} \right) $$ (4) where the angle of the optical axis of the corresponding half-wave plate is θj/2. Each wave plate can be configured into one of the four different angles to prepare equal superposition encoding the assignment of the two variables (x2j−1, x2j) as 00, 01, 10 or 11. As a result, the overall transformation U can prepare arbitrary proper states. For the cheating Merlins, the wave plates are set into angles differing from the honest case to implement an unequal splitting and (or) a different transformation U. The details on proof encoding are given in the Supplementary Information.
Stage (ⅱ) comprises a sequence of tunable permutations, each consisting of a transformation U and a mode routing. In this case the two-mode transformations {uj(θj)} are set to two-mode X or Z operations to permutate the two modes or not. The operation of the mode routing is equivalent to a fixed permutation. For example, one of the permutation matrix for mode routing in our experiment can be described as
$$ P_0 = \left( {\begin{array}{*{20}{l}} 0 \hfill & 1 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 0 \hfill & 0 \hfill & 0 \hfill & 1 \hfill & 0 \hfill & 0 \hfill \\ 1 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 1 \hfill \\ 0 \hfill & 0 \hfill & 1 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \\ 0 \hfill & 0 \hfill & 0 \hfill & 0 \hfill & 1 \hfill & 0 \hfill \end{array}} \right) $$ The combination of the aforementioned two operations enables programmable permutation P · U on the n optical modes. With a sequence of O(n) tunable permutation modules, the circuit can be programmed to perform all the permutations required for the two tests (See Supplementary Information for details).
In Stage (ⅲ), the first layer of two-mode transformations {uj(θj)} are all configured as two-mode Hadamard operations $H = \frac{1}{{\sqrt {2n} }}\left({\begin{array}{*{20}{l}} 1 \hfill & 1 \hfill \\ 1 \hfill & { - 1} \hfill \end{array}} \right)$ to interfere each of the n/2 pairs of the two optical modes (2j − 1, 2j). The following mode routing rearranges the optical modes to enable possible further interferences required by the satisfiability test. This routing is realized by a high extinction-ratio polarizing beam-splitter (PBS). Two different types of configurations are adopted for the second layer of {uj(θj)} depending on which of the satisfiability test and uniformity test is applied. If the uniformity test is chosen, all the transformations in this layer are set to Z gates or identity operators $I = \frac{1}{{\sqrt n }}\left({\begin{array}{*{20}{l}} 1 \hfill & 0 \hfill \\ 0 \hfill & 1 \hfill \end{array}} \right)$ (without placing any operation on the two modes), which do not perform any interference. Therefore each mode corresponds to an outcome of the form |i〉 ± |j〉 for a certain matching M in terms of the permutation. Arthur will reject the proof when the outcomes {|i〉 + |j〉, |i〉 − |j〉} both occur, that is, the two detectors (1, 4), (2, 5) or (3, 6) labelled in Fig. 1c both click among the measurements on K copies. For the satisfiability test, part of transformations in the last layer of {uj(θj)} are set into two-mode Hadamard operations to further interfere two adjacent modes after the aforementioned mode routing. Finally, one of the output modes (the "rejection mode") for a group (i, j, k, l) corresponds to the outcome |i〉 + |j〉 + |k〉 + |l〉, thus Arthur can decide to reject or accept the proof based on whether the detector coupled to the rejection mode clicks (see Supplementary Information for details).
The whole experimental set-up can form various Jamin–Lebedeff interferometers for different permutations and transformations. The beam displacers are strictly aligned and calibrated in order to maintain high interference visibilities for the interferometers when altering the permutations and transformations. The interference visibility for this type of interferometers is measured to be 99.4%. Each of the six output modes of the circuit is coupled to a single-photon avalanche diode (Excelitas Technologies, SPCM-800-FC). Detection events are recorded by a time-correlated single-photon counting system (Swabian Instruments, Time Tagger Ultra) with a coincidence window of 4 ns. We register the measurement results of 5000 × K photons for each test to provide the rejection probabilities shown in the figures.
-
Two single photons are injected into two proof encoding modules respectively to prepare the two quantum states |ψ1〉 and |ψ2〉, which yield the input field
$$ \begin{array}{l}|\psi _{{{{\mathrm{in}}}}}\rangle = |\psi _1\rangle |\psi _2\rangle \\ \qquad\,\,= \left( {\mathop {\sum}\nolimits_{i = 1}^n {\alpha _{1,i}\hat a_{1,i}^{\dagger} |0\rangle _1} } \right)\left( {\mathop {\sum}\nolimits_{j = 1}^n {\alpha _{2,j}\hat a_{2,j}^{\dagger} |0\rangle _2} } \right)\\ \qquad\,\,= \mathop {\sum}\nolimits_{i,j}^n {\alpha _{1,i}\alpha _{2,j}\hat a_{1,i}^{\dagger} \hat a_{2,j}^{\dagger} |0\rangle _1|0\rangle _2} \end{array} $$ (5) Here |0〉1 and |0〉2 represent the vacuum state for the two input sides. Then the two single-photon states interfere at the 50:50 NPBS for a multi-mode HOM interference. To observe the HOM interference, the fibre coupler labelled in Fig. 4a is moved by an electronically controlled translation stage (Thorlabs PT1-Z8) to change the relative delay between the wave packets of the two photons. The relationships between the creation operators for the input fields and output fields of the NPBS can be written as
$$ \begin{array}{l}\hat a_{1,i}^{\dagger} = \frac{1}{{\sqrt 2 }}\left( {\hat a_{3,i}^{\dagger} + \hat a_{4,i}^{\dagger} } \right) \\ \hat a_{2,i}^{\dagger} = \frac{1}{{\sqrt 2 }}\left( {\hat a_{3,i}^{\dagger} - \hat a_{4,i}^{\dagger} } \right)\end{array} $$ (6) By substituting Eq. (6) into Eq. (5), we obtain the output field
$$ \begin{array}{l}|\psi _{{{{\mathrm{out}}}}}\rangle = \mathop {\sum}\nolimits_{i,j}^n {\frac{{\alpha _{1,i}\alpha _{2,j}}}{2}\left( {\hat a_{3,i}^{\dagger} + \hat a_{4,i}^{\dagger} } \right)\left( {\hat a_{3,j}^{\dagger} - \hat a_{4,j}^{\dagger} } \right)|0\rangle _3|0\rangle _4} \\ \qquad\quad= \mathop {\sum}\nolimits_i {\frac{{\alpha _{1,i}\alpha _{2,i}}}{2}\left[ {\left( {\hat a_{3,i}^{\dagger} } \right)^2 - \left( {\hat a_{4,i}^{\dagger} } \right)^2} \right]|0\rangle _3|0\rangle _4} \\ \qquad\qquad+ \mathop {\sum}\nolimits_{i,j}^{i \ne j} {\frac{{\alpha _{1,i}\alpha _{2,j}}}{2}\left( {\hat a_{3,i}^{\dagger} \hat a_{3,j}^{\dagger} - \hat a_{4,i}^{\dagger} \hat a_{4,j}^{\dagger} } \right)|0\rangle _3|0\rangle _4} \\ \qquad\qquad+ \mathop {\sum}\nolimits_{i,j}^{i \ne j} {\frac{{\alpha _{1,i}\alpha _{2,j}}}{2}\left( {\hat a_{4,i}^{\dagger} \hat a_{3,j}^{\dagger} - \hat a_{3,i}^{\dagger} \hat a_{4,j}^{\dagger} } \right)|0\rangle _3|0\rangle _4} \end{array} $$ (7) For indistinguishable photons, the resulting output state can be represented as
$$ \begin{array}{l}|\psi _{{{{\mathrm{out}}}}}\rangle = \mathop {\sum}\nolimits_i {\frac{{\alpha _{1,i}\alpha _{2,i}}}{{\sqrt 2 }}\left( {|2_i\rangle _3|0\rangle _4 - |0\rangle _3|2_i\rangle _4} \right)} \\ \qquad\qquad+ \mathop {\sum}\nolimits_{i,j}^{i < j} {\frac{{\alpha _{1,i}\alpha _{2,j} + \alpha _{1,j}\alpha _{2,i}}}{2}\left( {|1_i,1_j\rangle _3|0\rangle _4 - |0\rangle _3|1_i,1_j\rangle _4} \right)} \\ \qquad\qquad+ \mathop {\sum}\nolimits_{i,j} {\frac{{\alpha _{1,i}\alpha _{2,j} - \alpha _{1,j}\alpha _{2,i}}}{2}|1_j\rangle _3|1_i\rangle _4} \end{array} $$ (8) Here |1i, 1j〉3 denotes the state with one photon in mode i and another photon in mode j for the output port 3. The right side of Eq. (8) contains three terms, where the first two correspond to the one-side terms (two photons are in the same output port) and the last one corresponds to the two-side terms (one photon in the output port 3 and another photon in the output port 4). The probability of finding a "two-side" outcome is
$$ \begin{array}{lll}p_r^{{{{\mathrm{swap}}}}} &= &\frac{1}{4}\mathop {\sum}\nolimits_{i,j} {\left| {\alpha _{1,i}\alpha _{2,j} - \alpha _{1,j}\alpha _{2,i}} \right|^2} \\ &=& \frac{1}{2}\mathop {\sum}\nolimits_{i,j} {|\alpha _{1,i}|^2|\alpha _{2,j}|^2 - \frac{1}{2}\mathop {\sum}\nolimits_{i,j} {\alpha _{1,i}^ \ast \alpha _{1,j}\alpha _{2,i}\alpha _{2,j}^ \ast } } \\ &= &\frac{1}{2}\left( {1 - |\langle \psi _1|\psi _2\rangle |^2} \right)\end{array} $$ (9) considering the overlap between the two states is $\langle \psi _1|\psi _2\rangle = \mathop {\sum}\nolimits_i {\alpha _{1, i}^ \ast \alpha _{2, i}}$. The probability $p_r^{{{{\mathrm{swap}}}}}$ is consistent with the probability of finding a "reject" outcome in a swap test. In the experiment, each path mode of the output is attached to a SPAD, therefore the two polarization modes in the same path are detected by the same detector. This reduces the number of outcomes from $\left({\begin{array}{*{20}{l}} n \hfill \\ 2 \hfill \end{array}} \right)$ to $\left({\begin{array}{*{20}{l}} {n/2} \hfill \\ 2 \hfill \end{array}} \right)$. The coincidence channels {1, 2}, {1, 3}, {2, 3}, {4, 5}, {4, 6}, {5, 6} correspond to the "accept" outcome (here {i, j} denotes a coincidence channel between detectors i and j as labelled in Fig. 4a). We also add photon number resolving detection by attaching a fiber beam-splitter (Thorlabs TN830R5F2) and an additional SPAD to two path modes. This scheme is capable of detecting more events on the "accept" outcome (see Supplementary Information for detailed results).