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 Aaronson et al. 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;

\item 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 subexponential 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 no-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 Arrazolla et al. 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.

Notations Used

• • $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].

Properties

• The protocol assumes that the original input qubit is unknown and the protocol is independent of the original input state (universality).
• The output copies are not identical and we are able to control the likelihood (fidelity) of the output copies to the original state by pre-preparing the ancillary states with special coefficients.
• Claims for General case:
  • Following inequality holds between the scaling factors $s_{0}$ and $s_{1}$
    

$s_{0}^{2}+s_{1}^{2}+s_{0}s_{1}-s_{0}-s_{1}\leq 0$

• • This elliptic inequality shows the possible value of the scaling parameters.
  • Trade-off inequality between the fidelities of the clones:
    

${\sqrt {(1-F_{a})(1-F_{b})}}\geq {\frac {1}{2}}-(1-F_{a})-(1-F_{b})$

• • Optimality is provided when the fidelities of two clones, $F_{a}$ and $F_{b}$, saturate the above inequality
• Claims for Special case with bell state:
  • Following ellipse equation holds between the scaling factors $a$ and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b}
    

$a^{2}+b^{2}+ab=1$

• • Following equations holds for fidelities of the clones:

$F_{a}=1-{\frac {b^{2}}{2}},F_{b}=1-{\frac {a^{2}}{2}}$

Pseudo Code

General Case

For more generality, we use the density matrix representation of the states which includes mixed states as well as pure states. For a simple pure state $|\psi \rangle$ the density matrix representation will be $\rho _{\psi }=|\psi \rangle \langle \psi |$. Let us assume the initial qubit to be in an unknown state $\rho _{\psi }$. Our task is to clone this qubit universally, i.e. input-state independently, in such a way, that we can control the scaling of the original and the clone at the output. In other words, we look for output which can be represented as below:
$\rho _{a}^{out}=s_{0}\rho _{\psi }+{\frac {1-s_{0}}{2}}{\hat {I}}$
$\rho _{b}^{out}=s_{1}\rho _{\psi }+{\frac {1-s_{1}}{2}}{\hat {I}}$
Here we assume that the original qubit after the cloning is “scaled” by the factor $s_{0}$, while the copy is scaled by the factor $s_{1}$. These two scaling parameters are not independent and they are related by a specific inequality.

Stage 1 Cloner State Preparation

1. Prepare the original qubit and two additional blank qubits $m$ and $n$ in pure states: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |0\rangle_{m_0} \otimes |0\rangle_{n_0} \equiv |00\rangle}
2. Prepare $|\psi \rangle _{m_{1},n_{1}}=c_{1}|00\rangle +c_{2}|01\rangle +c_{3}|10\rangle +c_{4}|11\rangle$, where the complex Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_i} coefficients will be specified so that the flow of information between the clones will be as desired.
   At this stage the original qubit is not involved, but this preparation stage will affect the fidelity of the clones at the end of the process.
3. To prepare the $|\psi \rangle _{m_{1},n_{1}}$ state, a Unitary gate must be performed so that:

$U|00\rangle =|\psi \rangle _{m_{1},n_{1}}$

• Use following relations to specify $c_{j}$ in terms of $a$ and $b$:
  

$c_{1}={\sqrt {\frac {s_{0}+s_{1}}{2}}}$, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_2 = \sqrt{\frac{1 - s_0}{2}}} , $c_{3}=0$, $c_{4}={\sqrt {\frac {1-s_{1}}{2}}}$
these $c_{j}$ satisfy the scaling equations and also the normalization condition of the state $|\psi \rangle _{m_{1},n_{1}}$. They are being used to control the flow of information between the clones

Stage 2 Cloning Circuit

• The cloning circuit consists of four CNOT gates acting on original and pre-prepared qubits from stage 2. We call the original qubit $|\psi \rangle _{in}$, ``first qubit", the first ancillary qubit of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\psi\rangle_{m_1,n_1}} , ``second qubit" and the second one, ``third qubit". The CNOT gates will act as follows:

1. First CNOT acts on first and second qubit while the first qubit is control and the second qubit is the target.
2. Second CNOT acts on first and third qubit while the first qubit is control and the third qubit is the target.
3. Third CNOT acts on first and second qubit while the second qubit is control and the first qubit is the target.
4. Forth CNOT acts on first and third qubit while the third qubit is control and the first qubit is the target.

• Mathematically the cloning part of the protocol can be shown as:
  

$|\psi \rangle _{out}=P_{3,1}P_{2,1}P_{1,3}P_{1,2}|\psi \rangle _{in}|\psi \rangle _{m_{1},n_{1}}$

Stage 3 Discarding ancillary state

• Discard one of the extra states. The output states will be the first and second (or third) output.
  
  

Special case with bell state:

Stage 1 Cloner state preparation

1. Prepare the original qubit and two additional blank qubits $m$ and $n$ in pure states: $|0\rangle _{m_{0}}\otimes |0\rangle _{n_{0}}\equiv |00\rangle$
2. Prepare $|\psi \rangle _{m_{1},n_{1}}=a|\Phi ^{+}\rangle _{m_{1},n_{1}}+b|0\rangle _{m_{1}}|+\rangle _{n_{1}}$, where $|\Phi ^{+}\rangle$ is a Bell state and $|+\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )$. In this case, the density matrix representation of the output states will be:
   

$\rho _{a}^{out}=(1-b^{2})|\psi \rangle \langle \psi |+{\frac {b^{2}}{2}}{\hat {I}}$
$\rho _{b}^{out}=(1-a^{2})|\psi \rangle \langle \psi |+{\frac {a^{2}}{2}}{\hat {I}}$
Stage 2 Cloning Circuit

• The cloning circuit is exactly the same as the general case. after the cloning circuit, the output state will be:
  

$a|\psi \rangle _{in}|\Phi ^{+}\rangle _{m,n}+b|\psi \rangle _{m}|\Phi ^{+}\rangle _{in,n}$ The reduced density matrix of two clones A and B can be written in terms of their fidelities:
$\rho _{a}^{out}=F_{a}|\psi \rangle \langle \psi |+(1-F_{a})|\psi ^{\perp }\rangle \langle \psi ^{\perp }|$
$\rho _{b}^{out}=F_{b}|\psi \rangle \langle \psi |+(1-F_{b})|\psi ^{\perp }\rangle \langle \psi ^{\perp }|$
Stage 3 Discarding ancillary state

• The same as the general case.

Further Information

*contributed by Federico Centrone