Verification of NP-complete problems

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, a honest but computationally bounded verifier, that he has the solution to a specific NP-complete problem. It was shown by ADS (2008) 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 in the classical world. These quantum class of problems is called QMA, as in Quantum Merlin Arthur, and is the generalization of NP problems as it consists to the class of languages that can be verified efficiently with quantum proofs.

Tags: Verification, Quantum Advantage, Communication Complexity, QMA, BQP, NP-complete, unentanglement.

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 unproven but very 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 state by pre-preparing the ancillary states with special coefficients.

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 ADS (2017) 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 believe a dishonest Merlin. To prevent this, Arthur chooses two copies at random and perform a SWAP test to see if they are the same quantum state.

Notation

• • $N:$ size of the problem
  • $x=\{x_{1}x_{2}...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}...|1\rangle _{i}...|0\rangle _{N}:$ state of one photon in the $i^{t}h$ 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^{t}h$ quantum proof encoding the assignment x
  • ${\mathcal {M}}$: set of all the possible matchings between two indices in [N].

Hardware Requirements

• Network Stage: Prepare and Measure
• Relevant Parameters:
  • $K=O({\sqrt {N}})$ single photon sources.
  • K fixed cascades of beamsplitters of depth $O(\log N)$ each 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 permutation of 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.

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 run in exponential time in the size of N.
• can be implemented with linear optics (not exclusively).
• It has been theorized that N needs to be at least about 500 in order to have the advantage over the best classical protocol.

Pseudocode

Stage 1 State Preparation

1. 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$.
2. Sends each copy $|\psi \rangle _{k}$ to Arthur through their quantum channel.
3. Arthur chooses at random which test to perform.

Stage 2 Satisfiability

1. Arthur partition the clauses in blocks so that each block contain at most one variable.
2. 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.
3. If he detects a photon in the first detector he rejects the proof, otherwise he accepts.

Stage 3 Uniformity

1. Arthur chooses a matching ${\mathcal {M}}$ over [N].
2. 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}}$ .
3. He rejects if for any (i,j) he detects a photon in both detectors.

Stage 4 Symmetry

1. Arthur chooses at random an index $k\in \{2,...,K\}$
2. Performs a SWAP test between $|\psi \rangle _{1}$ and $|\psi \rangle _{k}$.
3. Accepts if SWAP test accepts.

Further Information

• Theoretical Papers
  • ADS (2017)
  • Tapp (2008)
  • ADBSF (2008)
• Experimental Papers There has not been any experimental implementation of this protocol so far.

*contributed by Federico Centrone