×

Quantum information and the PCP theorem. (English) Zbl 1192.68280

Summary: Our main result is that the membership \(x\in SAT\) (for \(x\) of length \(n\)) can be proved by a logarithmic-size quantum state \(|\Psi \rangle \), together with a polynomial-size classical proof consisting of blocks of length \(poly\log (n)\) bits each, such that after measuring the state \(|\Psi \rangle \) the verifier only needs to read one block of the classical proof. This shows that if a short quantum witness is available then a (classical) PCP with only one query is possible.
Our second result is that the class \(QIP/qpoly\) contains all languages. That is, for any language \(L\) (even non-recursive), the membership \(x\in L\) (for \(x\) of length \(n\)) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state \(|\Psi _{L,n }\rangle \) (depending only on \(L\) and \(n\)). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical. The advice \(|\Psi _{L,n }\rangle \) given to the verifier can also be replaced by a classical probabilistic advice, as long as this advice is kept as a secret from the prover. Our result can hence be interpreted as: the class \(IP/rpoly\) contains all languages.
For the proof of the second result, we introduce the quantum low-degree-extension of a string of bits. The main result requires an additional machinery of quantum low-degree-test.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
81P68 Quantum computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aaronson, S.: Limitations of quantum advice and one-way communication. Theory Comput. 1(1), 1–28 (2005) · Zbl 1213.68278 · doi:10.4086/toc.2005.v001a001
[2] Aharonov, D.: Quantum Computation–A Review. In: Stauffer, D. (ed.) Annual Review of Computational Physics, vol. VI. World Scientific, Singapore (1998) · Zbl 1219.81088
[3] Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (1998) · Zbl 1065.68570 · doi:10.1145/278298.278306
[4] Ambainis, A., Nayak, A., Ta-Shma, A., Vazirani, U.V.: Dense quantum coding and quantum finite automata. J. ACM 49(4), 496–511 (2002) · Zbl 1326.68133 · doi:10.1145/581771.581773
[5] Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70–122 (1998) · Zbl 0903.68076 · doi:10.1145/273865.273901
[6] Arora, S., Sudan, M.: Improved low-degree testing and its applications. Combinatorica 23(3), 365–426 (2003) · Zbl 1101.68572 · doi:10.1007/s00493-003-0025-0
[7] Babai, L.: Trading group theory for randomness. STOC 421–429 (1985)
[8] Babai, L., Moran, S.: Arthur-merlin games: a randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254–276 (1988) · Zbl 0652.03029 · doi:10.1016/0022-0000(88)90028-1
[9] Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3–40 (1991) · Zbl 0774.68041 · doi:10.1007/BF01200056
[10] Cleve, R., Hoyer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. IEEE Conf. Comput. Complex. (2004) 236–249
[11] Dinur, I., Fischer, E., Kindler, G., Raz, R., Safra, S.: PCP characterizations of NP: towards a polynomially-small error-probability. STOC 29-40 (1999). Full version in http://www.wisdom.weizmann.ac.il/\(\sim\)ranraz/publications · Zbl 1234.68133
[12] Feige, U., Goldwasser, S., Lovasz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268–292 (1996) · Zbl 0882.68129 · doi:10.1145/226643.226652
[13] Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989) · Zbl 0677.68062 · doi:10.1137/0218012
[14] Holevo, A.S.: Some estimates for the amount of information transmittable by a quantum communications channel. Probl. Peredaci Inf. 9(3), 3–11 (1973). English translation: Probl. Inf. Trans. 9(3), 177–183 (1973) · Zbl 0317.94003
[15] Kitaev, A., Watrous, J.: Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. STOC 608–617 (2000) · Zbl 1296.68057
[16] Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39(4), 859–868 (1992) · Zbl 0799.68097 · doi:10.1145/146585.146605
[17] Moshkovitz, D., Raz, R.: Sub-constant error low degree test of almost-linear size. STOC 21–30 (2006) · Zbl 1301.68128
[18] Nayak, A.: Optimal lower bounds for quantum automata and random access codes. FOCS 369–377 (1999)
[19] Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000) · Zbl 1049.81015
[20] Nishimura, H., Yamakami, T.: Polynomial time quantum computation with advice. Electronic Colloquium on Computational Complexity (ECCC)(059) (2003) · Zbl 1177.68101
[21] Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763–803 (1998) · Zbl 0911.68082 · doi:10.1137/S0097539795280895
[22] Raz, R., Safra, S.: A sub-constant error-probability low-degree test and a sub-constant error-probability PCP characterization of NP. STOC 475–484 (1997) · Zbl 0963.68175
[23] Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252–271 (1996) · Zbl 0844.68062 · doi:10.1137/S0097539793255151
[24] Shamir, A.: IP=PSPACE. J. ACM 39(4), 869–877 (1992) · Zbl 0799.68096 · doi:10.1145/146585.146609
[25] Watrous, J.: PSPACE has constant-round quantum interactive proof systems. Theor. Comput. Sci. 292(3), 575–588 (2003) · Zbl 1026.68121 · doi:10.1016/S0304-3975(01)00375-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.