Write, autoreview, editor, reviewer
3,125
edits
Verification of NP-complete problems: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
| 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> | 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 [[Verification of NP-complete problems#References|(ADS (2008 | 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 [[Verification of NP-complete problems#References|(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.</br> | ||
'''Tags:''' Verification, Quantum Advantage, Communication Complexity, QMA, BQP, NP-complete, unentanglement. | '''Tags:''' Verification, Quantum Advantage, Communication Complexity, QMA, BQP, NP-complete, unentanglement. | ||
| Line 14: | Line 14: | ||
==Outline== | ==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 [[ | 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 [[Verification of NP-complete problems#References|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). | *'''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. | *'''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. | ||