Revision History for: Verification of NP-complete problems
- 2025-05-22 at 15:12 by JuliaM
Introduction
The aim of the protocol is to verify NP-complete problems in the context of communication complexity, so in the case in which the amount of communication between the involved parties is a resource. By definition, if a problem is in NP then it is possible to verify efficiently if a given solution is correct. However, if the given solution, or witness, is incomplete, then the verification process is exponential in the size of the missing information.
In this setting, Merlin, an overpowerful but untrusted prover, wants to convince Arthur, an honest but computationally bounded verifier, that he has the solution to a specific NP-complete problem. It was shown by [1] that if Merlin sends quantum proofs revealing only partial information about the complete solution, Arthur can efficiently verify it in a probabilistic sense, giving rise to a computational advantage with no analogous one in the classical world. This quantum class of problems is called QMA, as in Quantum Merlin Arthur, and is the generalisation of NP problems, as it consists of the class of languages that can be verified efficiently with quantum proofs.Outline
In order to verify an N-size 2-out-of-4SAT problem, Merlin is required to send the proof encrypted in the phase of a quantum state in a superposition of N orthogonal modes. Furthermore, he will need to send order $\\\sqrt{N}$ identical copies of this quantum state. However, due to the Holevo bound, Arthur can retrieve at most order $\\\sqrt {N}\\\log _{2}(N)$ bits of information on average by just measuring the state, which is only a small fraction of the whole N bits solution. Therefore, to verify the correctness of the proof and the honesty of Merlin, Arthur will need to perform three distinct tests. In [1], they specify how these tests could be performed using a single photon source and linear optics, so in the following we will refer to it, even though the protocol can be implemented with any quantum information carriers. Each test is performed with probability 1/3.
- Satisfiability Test: In this test, Arthur chooses one of the copies of the quantum proofs and verifies that Merlin’s assignment is correct, i.e. it solves his 2-out-of-4 SAT for some clauses. Because of the probabilistic nature of the protocol, he will only be able to verify some of the clauses and will reject only if he detects incorrectness (so he will accept even if he does not detect anything at all).
- Uniformity Test: Merlin can cheat by sending a state which is not proper, in which case the satisfiability test might accept even if there is no correct assignment to the problem. In order to avoid this, Arthur can perform a test on all the proofs to check if the incoming states are in the expected form.
- Symmetry Test: The quantum proofs might not be identical, which might mislead Arthur into believing a dishonest Merlin. To prevent this, Arthur chooses two copies at random and performs a SWAP test to see if they are the same quantum state.
Assumptions
- The problem must be a balanced formula, meaning that every variable occurs in at most a constant number of clauses.
- It must be a PCP, i.e. either the formula is satisfiable, or at least a fraction of the clauses must be unsatisfiable;
- Exponential time hypothesis, i.e. any NP-complete problem cannot be solved in sub-exponential time in the worst case.
- There is a promise of no entanglement between the quantum proofs.
The first two conditions are always met when reducing the NP problem to a 3SAT and then to a 2-out-of-4SAT. The exponential hypothesis is an unproven but highly accredited conjecture which implies that $P\\\neq NP$.
The un-entanglement promise is typical in these scenarios, as it was proved that Merlin can always cheat by entangling the proofs, and there is no way for Arthur to verify the state by pre-preparing the ancillary states with special coefficients.
Requirements
Network Stage: Prepare and Measure
Relevant Parameters:
- $K = O(\\\sqrt{N})$ single-photon sources.
- $K$ fixed cascades of beamsplitters, each of depth $O(\\\log N)$, preparing a single photon in an equal superposition over $N$ modes.
- $KN$ phase-shifters, one for each mode.
- One $K \\\times K$ block switch that permutes groups of $N$ modes.
- $KN \\\times N$ active switches that perform arbitrary permutations of $N$ modes.
- One $2N \\\times 2N$ switch performing a permutation over $2N$ modes.
- $O(N)$ four-mode interferometers for the satisfiability test.
- $O(KN)$ two-mode interferometers for uniformity and symmetry tests.
- $O(KN)$ photon number resolving detectors.
Notation
- $N$: size of the problem
- $x = \\\{x_1, x_2, \\\dots, x_N\\\}$: Merlin’s assignment to solve the problem
- $K = O(\\\sqrt{N})$: number of copies of the quantum proof
- $|i\\\rangle = |0\\\rangle_1 |0\\\rangle_2 \\\dots |1\\\rangle_i \\\dots |0\\\rangle_N$: state of one photon in the $i^{\\\text{th}}$ optical mode and zero in the others
- $|\\\psi_x\\\rangle_k = \\\frac{1}{\\\sqrt{N}} \\\sum_{i=1}^{N} (-1)^{x_i} |i\\\rangle$: $k^{\\\text{th}}$ quantum proof encoding the assignment $x$
- $\\\mathcal{M}$: set of all possible matchings between two indices in $[N]$
Properties
The protocol:
- Involves two parties and one-way communication from the prover to the verifier.
- Assumes that anyone might be dishonest and still provide perfect completeness and constant soundness.
- Has a communication complexity of $O({\\\sqrt {N}}\\\log _{2}N)$ bits of information.
- Runs in exponential time, while it can be shown that by using classical proofs, the best protocol runs in exponential time in the size of N.
- Can be implemented with linear optics (not exclusively).
- It has been theorised that N needs to be at least about 500 in order to have the advantage over the best classical protocol.
Technical Description
- Stage 1: State Preparation
- Merlin prepares $K=O({\\\sqrt {N}})$ copies of the state $|\\\psi _{x}\\\rangle _{k}={\\\frac {1}{\\\sqrt {N}}}\\\sum _{i=1}^{N}(-1)^{x_{i}}|i\\\rangle$.
- Sends each copy $|\\\psi \\\rangle _{k}$ to Arthur through their quantum channel.
- Arthur chooses at random which test to perform.
- Stage 2 Satisfiability:
- Arthur partitions the clauses into blocks so that each block contains at most one variable.
- He decides at random which block to use and prepares his interferometers so that for each clause, the respective optical modes will interfere as in the figure.
- If he detects a photon in the first detector, he rejects the proof, otherwise, he accepts.
- Stage 3 Uniformity:
- Arthur chooses a matching ${\\\mathcal {M}}$ over [N].
- He then measures each copy in the basis $\\\frac {|i\\\rangle +|j\\\rangle }{\\\sqrt {2}}, \\\frac {|i\\\rangle -|j\\\rangle }{\\\sqrt {2}}$, $\\\forall (i,j)\\\in {\\\mathcal {M}}$.
- He rejects if for any (i,j) he detects a photon in both detectors.
- Stage 4 Symmetry:
- Arthur chooses at random an index $k\\\in \\\{2,…,K\\\}$
- Performs a SWAP test between $|\\\psi \\\rangle _{1}$ and $|\\\psi \\\rangle _{k}$.
- Accepts if the SWAP test accepts.
Experimental Implementations
There has not been any experimental implementation of this protocol so far.
Further Information
Theoretically relevant papers are [1], [2]
References
- Arrazola, Juan Miguel, Eleni Diamanti, and Iordanis Kerenidis. “Quantum superiority for verifying NP-complete problems with linear optics.” npj Quantum Information 4, no. 1 (2018): 56.
- Aaronson, Scott, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. “The power of unentanglement.” In 2008 23rd Annual IEEE Conference on Computational Complexity, pp. 223-236. IEEE, 2008.
- 2025-05-16 at 17:50 by Mina Doosti
Introduction
The aim of the protocol is to verify NP-complete problems in the context of communication complexity, so in the case in which the amount of communication between the involved parties is a resource. By definition, if a problem is in NP then it is possible to verify efficiently if a given solution is correct. However, if the given solution, or witness, is incomplete, then the verification process is exponential in the size of the missing information.
In this setting, Merlin, an overpowerful but untrusted prover, wants to convince Arthur, an honest but computationally bounded verifier, that he has the solution to a specific NP-complete problem. It was shown by [1] that if Merlin sends quantum proofs revealing only partial information about the complete solution, Arthur can efficiently verify it in a probabilistic sense, giving rise to a computational advantage with no analogous one in the classical world. This quantum class of problems is called QMA, as in Quantum Merlin Arthur, and is the generalisation of NP problems, as it consists of the class of languages that can be verified efficiently with quantum proofs.Outline
In order to verify an N-size 2-out-of-4SAT problem, Merlin is required to send the proof encrypted in the phase of a quantum state in a superposition of N orthogonal modes. Furthermore, he will need to send order $sqrt{N}$ identical copies of this quantum state. However, due to the Holevo bound, Arthur can retrieve at most order $sqrt {N}log _{2}(N)$ bits of information on average by just measuring the state, which is only a small fraction of the whole N bits solution. Therefore, to verify the correctness of the proof and the honesty of Merlin, Arthur will need to perform three distinct tests. In [1], they specify how these tests could be performed using a single photon source and linear optics, so in the following we will refer to it, even though the protocol can be implemented with any quantum information carriers. Each test is performed with probability 1/3.
- Satisfiability Test: In this test, Arthur chooses one of the copies of the quantum proofs and verifies that Merlin’s assignment is correct, i.e. it solves his 2-out-of-4 SAT for some clauses. Because of the probabilistic nature of the protocol, he will only be able to verify some of the clauses and will reject only if he detects incorrectness (so he will accept even if he does not detect anything at all).
- Uniformity Test: Merlin can cheat by sending a state which is not proper, in which case the satisfiability test might accept even if there is no correct assignment to the problem. In order to avoid this, Arthur can perform a test on all the proofs to check if the incoming states are in the expected form.
- Symmetry Test: The quantum proofs might not be identical, which might mislead Arthur into believing a dishonest Merlin. To prevent this, Arthur chooses two copies at random and performs a SWAP test to see if they are the same quantum state.
Assumptions
- The problem must be a balanced formula, meaning that every variable occurs in at most a constant number of clauses.
- It must be a PCP, i.e. either the formula is satisfiable, or at least a fraction of the clauses must be unsatisfiable;
- Exponential time hypothesis, i.e. any NP-complete problem cannot be solved in sub-exponential time in the worst case.
- There is a promise of no entanglement between the quantum proofs.
The first two conditions are always met when reducing the NP problem to a 3SAT and then to a 2-out-of-4SAT. The exponential hypothesis is an unproven but highly accredited conjecture which implies that $Pneq NP$.
The un-entanglement promise is typical in these scenarios, as it was proved that Merlin can always cheat by entangling the proofs, and there is no way for Arthur to verify the state by pre-preparing the ancillary states with special coefficients.
Requirements
Network Stage: Prepare and Measure
Relevant Parameters:
- $K = O(sqrt{N})$ single-photon sources.
- $K$ fixed cascades of beamsplitters, each of depth $O(log N)$, preparing a single photon in an equal superposition over $N$ modes.
- $KN$ phase-shifters, one for each mode.
- One $K times K$ block switch that permutes groups of $N$ modes.
- $KN times N$ active switches that perform arbitrary permutations of $N$ modes.
- One $2N times 2N$ switch performing a permutation over $2N$ modes.
- $O(N)$ four-mode interferometers for the satisfiability test.
- $O(KN)$ two-mode interferometers for uniformity and symmetry tests.
- $O(KN)$ photon number resolving detectors.
Notation
- $N$: size of the problem
- $x = {x_1, x_2, dots, x_N}$: Merlin’s assignment to solve the problem
- $K = O(sqrt{N})$: number of copies of the quantum proof
- $|irangle = |0rangle_1 |0rangle_2 dots |1rangle_i dots |0rangle_N$: state of one photon in the $i^{text{th}}$ optical mode and zero in the others
- $|psi_xrangle_k = frac{1}{sqrt{N}} sum_{i=1}^{N} (-1)^{x_i} |irangle$: $k^{text{th}}$ quantum proof encoding the assignment $x$
- $mathcal{M}$: set of all possible matchings between two indices in $[N]$
Properties
The protocol:
- Involves two parties and one-way communication from the prover to the verifier.
- Assumes that anyone might be dishonest and still provide perfect completeness and constant soundness.
- Has a communication complexity of $O({sqrt {N}}log _{2}N)$ bits of information.
- Runs in exponential time, while it can be shown that by using classical proofs, the best protocol runs in exponential time in the size of N.
- Can be implemented with linear optics (not exclusively).
- It has been theorised that N needs to be at least about 500 in order to have the advantage over the best classical protocol.
Technical Description
- Stage 1: State Preparation
- Merlin prepares $K=O({sqrt {N}})$ copies of the state $|psi _{x}rangle _{k}={frac {1}{sqrt {N}}}sum _{i=1}^{N}(-1)^{x_{i}}|irangle$.
- Sends each copy $|psi rangle _{k}$ to Arthur through their quantum channel.
- Arthur chooses at random which test to perform.
- Stage 2 Satisfiability:
- Arthur partitions the clauses into blocks so that each block contains at most one variable.
- He decides at random which block to use and prepares his interferometers so that for each clause, the respective optical modes will interfere as in the figure.
- If he detects a photon in the first detector, he rejects the proof, otherwise, he accepts.
- Stage 3 Uniformity:
- Arthur chooses a matching ${mathcal {M}}$ over [N].
- He then measures each copy in the basis $frac {|irangle +|jrangle }{sqrt {2}}, frac {|irangle -|jrangle }{sqrt {2}}$, $forall (i,j)in {mathcal {M}}$.
- He rejects if for any (i,j) he detects a photon in both detectors.
- Stage 4 Symmetry:
- Arthur chooses at random an index $kin {2,…,K}$
- Performs a SWAP test between $|psi rangle _{1}$ and $|psi rangle _{k}$.
- Accepts if the SWAP test accepts.
Experimental Implementations
There has not been any experimental implementation of this protocol so far.
Further Information
Theoretically relevant papers are [1], [2]
References
- Arrazola, Juan Miguel, Eleni Diamanti, and Iordanis Kerenidis. “Quantum superiority for verifying NP-complete problems with linear optics.” npj Quantum Information 4, no. 1 (2018): 56.
- Aaronson, Scott, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor. “The power of unentanglement.” In 2008 23rd Annual IEEE Conference on Computational Complexity, pp. 223-236. IEEE, 2008.