Editing 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.</br>
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.</br>

'''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 <math>P\neq NP</math>. 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 <math>\sqrt{N}</math> identical copies of this quantum state. However, due to the Holevo bound, Arthur can retrieve at most order <math>\sqrt{N}\log_2 N</math> 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==
**<math>N:</math> size of the problem
**<math>x=\{x_1 x_2 ... x_N\}:</math> Merlin's assignment to solve the problem
**<math>K=O(\sqrt{N}):</math> number of copies of the quantum proof
**<math>|i\rangle=|0\rangle_1|0\rangle_2...|1\rangle_i...|0\rangle_N:</math> state of one photon in the <math>i^th</math> optical mode and zero in the others
**<math>|\psi_x\rangle_k=\frac{1}{\sqrt{N}}\sum_{i=1}^N(-1)^{x_i}|i\rangle:</math> <math>k^th</math> quantum proof encoding the assignment x
**<math>\mathcal{M}</math>: set of all the possible matchings between two indices in [N].
==Hardware Requirements==
* '''Network Stage:''' [[:Category: Prepare and Measure Network Stage|Prepare and Measure]][[Category: Prepare and Measure Network Stage]]
* '''Relevant Parameters:'''
** <math>K=O(\sqrt{N}</math> single photon sources.
** K fixed   cascades   of   beamsplitters   of   depth <math>O(\log N)</math> each  preparing  a  single  photon  in  an equal superposition over N modes.
** KN phase-shifters, one for each mode.
** One <math>K\times K</math> block switch that permutes groups of N modes.
** <math>K N\times N</math> active switches that perform arbitrary permutations of N modes.
** One <math>2N\times 2N</math> 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 <math>O(\sqrt{N}\log_2N)</math> 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.

==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 <math>|\psi\rangle</math> the density matrix representation will be <math>\rho_{\psi} = |\psi\rangle\langle\psi|</math>. Let us assume the initial qubit to be in an unknown state <math>\rho_{\psi}</math>. 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:</br>
<math>\rho_{a}^{out} = s_0 \rho_{\psi} + \frac{1 - s_0}{2} \hat{I}</math></br>
<math>\rho_{b}^{out} = s_1 \rho_{\psi} + \frac{1 - s_1}{2} \hat{I}</math></br>
Here we assume that the original qubit after the cloning is “scaled” by the factor <math>s_0</math>, while the copy is scaled by the factor <math>s_1</math>. These two scaling parameters are not independent and they are related by a specific inequality.</br></br>
<u>'''Stage 1'''</u> Cloner State Preparation
# Prepare the original qubit and two additional blank qubits <math>m</math> and <math>n</math> in pure states: <math>|0\rangle_{m_0} \otimes |0\rangle_{n_0} \equiv |00\rangle</math>
#Prepare <math>|\psi\rangle_{m_1,n_1} = c_1|00\rangle + c_2|01\rangle + c_3|10\rangle + c_4|11\rangle</math>, where the complex <math>c_i</math> coefficients will be specified so that the flow of information between the clones will be as desired. </br>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. 
#To prepare the <math>|\psi\rangle_{m_1,n_1}</math> state, a Unitary gate must be performed so that: 
<math>U|00\rangle = |\psi\rangle_{m_1,n_1}</math> 
*Use following relations to specify <math>c_j</math> in terms of <math>a</math> and <math>b</math>:</br>
<math>c_1 = \sqrt{\frac{s_0 + s_1}{2}}</math>, <math>c_2 = \sqrt{\frac{1 - s_0}{2}}</math>, <math>c_3 = 0</math>, <math>c_4 = \sqrt{\frac{1 - s_1}{2}}</math></br>
these <math>c_j</math> satisfy the scaling equations and also the normalization condition of the state <math>|\psi\rangle_{m_1,n_1}</math>. They are being used to control the flow of information between the clones</br></br>
<u>'''Stage 2'''</u> 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 <math>|\psi\rangle_{in}</math>, ``first qubit", the first ancillary qubit of <math>|\psi\rangle_{m_1,n_1}</math>, ``second qubit" and the second one, ``third qubit". The CNOT gates will act as follows:
#First CNOT acts on first and second qubit while the first qubit is control and the second qubit is the target.
#Second CNOT acts on first and third qubit while the first qubit is control and the third qubit is the target.
# Third CNOT acts on first and second qubit while the second qubit is control and the first qubit is the target.
# 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:</br>
<math>|\psi\rangle_{out} = P_{3,1} P_{2,1} P_{1,3} P_{1,2} |\psi\rangle_{in} |\psi\rangle_{m_1,n_1}</math></br></br>
<u>'''Stage 3'''</u> Discarding ancillary state
*Discard one of the extra states. The output states will be the first and second (or third) output.</br></br>
===Special case with bell state:===
<u>'''Stage 1'''</u> Cloner state preparation
# Prepare the original qubit and two additional blank qubits <math>m</math> and <math>n</math> in pure states: <math>|0\rangle_{m_0} \otimes |0\rangle_{n_0} \equiv |00\rangle</math>
# Prepare <math>|\psi\rangle_{m_1,n_1} = a|\Phi^{+}\rangle_{m_1,n_1} + b|0\rangle_{m_1} |+\rangle_{n_1}</math>, where <math>|\Phi^{+}\rangle</math> is a [[Bell state]] and <math>|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)</math>. In this case, the density matrix representation of the output states will be:</br>
<math>\rho_{a}^{out} = (1 - b^2) |\psi\rangle\langle\psi| + \frac{b^2}{2} \hat{I}</math></br>
<math>\rho_{b}^{out} = (1 - a^2) |\psi\rangle\langle\psi| + \frac{a^2}{2} \hat{I}</math></br>
<u>'''Stage 2'''</u> Cloning Circuit
* The cloning circuit is exactly the same as the general case. after the cloning circuit, the output state will be:</br>
<math>a|\psi\rangle_{in} |\Phi^+\rangle_{m,n} + b|\psi\rangle_m |\Phi^+\rangle_{in,n}</math>
The reduced density matrix of two clones A and B can be written in terms of their fidelities:</br>
<math>\rho_{a}^{out} = F_a |\psi\rangle\langle\psi| + (1 - F_a)|\psi^{\perp}\rangle\langle\psi^{\perp}|</math></br>
<math>\rho_{b}^{out} = F_b |\psi\rangle\langle\psi| + (1 - F_b)|\psi^{\perp}\rangle\langle\psi^{\perp}|</math></br>
<u>'''Stage 3'''</u> Discarding ancillary state
* The same as the general case.

==Further Information==
<div style='text-align: right;'>''*contributed by Federico Centrone''</div>