Verification of NP-complete problems: Difference between revisions

Verification of NP-complete problems (edit)

Revision as of 11:04, 18 April 2019

326 bytes removed , 18 April 2019

no edit summary

Shraddha

Write, autoreview, editor, reviewer

3,125

edits

@@ Line 1: / Line 1: @@
+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>
-This protocol achieves the functionality of [[Quantum Cloning]]. Asymmetric universal cloning refers to a quantum cloning machine (QCM) where its output clones are not the same or in other words, they have different [[fidelities]]. Here we focus on <math>1 \rightarrow 1 + 1</math> universal cloning. In asymmetric cloning, we try to distribute information unequally among the copies. A trade-off relation exists between the fidelities, meaning if one of the copies are very close to the original state, the other one will be far from it. There are two approaches to this kind of cloning, both leading to same trade-off relation. Here we discuss the quantum circuit approach (Buzek et al., 1997) It can be also noted that the symmetric universal <math>1 \rightarrow 2</math> cloning can be considered as a special case of the asymmetric universal cloning where the information between copies has been equally distributed.
+'''Tags:''' Verification, Quantum Advantage, Communication Complexity, QMA, BQP, NP-complete, unentanglement.
-'''Tags:''' [[Category: Building Blocks]][[:Category: Building Blocks|Building Blocks]], [[Quantum Cloning]], Universal Cloning, asymmetric cloning, copying quantum states, [[:Category: Quantum Functionality|Quantum Functionality]][[Category: Quantum Functionality]], [[:Category:Specific Task|Specific Task]][[Category:Specific Task]],symmetric or [[Optimal Universal N-M Cloning|Optimal or Symmetric Cloning]], [[Probabilistic Cloning]]
 ==Assumptions==
-* We assume that the original input qubit is unknown and the protocol is independent of the original input state (universality).
+* The problem must be a ''[[balanced formula]]'', meaning that every variable occurs in at most a constant number of clauses;
-* 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.
+\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 this protocol, there are three main stages. The first stage is a preparation stage. we prepare two ancillary states with special coefficients which will lead to the desired flow of the information between copied states. The original state will not be engaged at this stage. At the second stage the cloner circuit will act on all the three states (the original and two other states) and at the second stage the two copied state will appear at two of the outputs and one of the outputs should be discarded. The Procedure will be as following:
+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.
-* Prepare two blank states and then perform a transformation taking these two states to a new state with pre-selected coefficients in such a way that the information distribution between two final states will be the desired.[[File:Asymmetriccloner.jpg|right|thumb|1000px| Graphical representation of the network for the asymmetric cloner. The CNOT gates are shown in the cloner section with control qubit (denoted as <math>\bullet</math> ) and a target qubit (denoted as <math>\circ</math> ). We separate the preparation of the quantum copier from the cloning process itself.]]
+*'''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).
-*Perform the cloner circuit. the cloner circuit consists of four CNOT gate acting in all the three input qubits.  For every CNOT gate, we have a control qubit (which indicates whether or not the CNOT should act) and a target qubit (which is the qubit that CNOT gate acts on it and flips it).
+*'''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.
-* The two asymmetric clones will appear at two of the outputs (depending on the preparation stage) and the other output should be discarded.
+*'''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>|\psi\rangle_{in}:</math>The original input state
+**<math>N:</math> size of the problem
-**<math>\rho_{\psi_{in}}:</math> The density matrix of the input pure state equal to <math>|\psi_{in}\rangle\langle\psi_{in}|</math>
+**<math>x=\{x_1 x_2 ... x_N\}:</math> Merlin's assignment to solve the problem
-**<math>s_0:</math> The scaling parameter of the first clone
+**<math>K=O(\sqrt{N}):</math> number of copies of the quantum proof
-**<math>s_12:</math> The scaling parameter of the second clone
+**<math>\ket{i}=\ket{0}_1\ket{0}_2...\ket{1}_i...\ket{0}_N:</math> state of one photon in the ith optical mode and zero in the others
-**<math>\rho_{a}^{out}:</math> The output density matrix of the first clone (equal to <math>|\psi_{a}^{out}\rangle\langle\psi_{a}^{out}|</math> if the output state is pure)
+**<math>\ket{\psi_x}_k=\frac{1}{\sqrt{N}}\sum_{i=1}^N(-1)^{x_i}\ket{i}:</math> kth quantum proof encoding the assignment x
-**<math>\rho_{b}^{out}:</math> The output density matrix of the second clone (equal to <math>|\psi_{b}^{out}\rangle\langle\psi_{b}^{out}|</math> if the output state is pure)
-**<math>\hat{I}:</math> The ``Identity" or completely mixed density matrix
-**<math>|0\rangle_{m_0} \otimes |0\rangle_{n_0} \equiv |00\rangle:</math> state of the ancillary qubits before preparation phase
-**<math>|\psi\rangle_{m_1,n_1}:</math>  state of the ancillary qubits after the preparation
-**<math>c_j:</math> amplitudes (or coefficients) of the prepared state $|\psi\rangle_{m_1,n_1}$. These coefficients are being used to control the flow of the information between the copies before starting the cloning process.
-**<math>P_{k,l}:</math> The CNOT gate where the control qubit is <math>k</math> and the target qubit is <math>l</math>
-**<math>|\psi\rangle_{out}:</math> The total output of the asymmetric cloning circuit
-**<math>|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle):</math> Bell state
-**<math>|+\rangle =  \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle):</math> Plus state. The eigenvector of Pauli X
 ==Properties==