RECORD
Quantum interactive proofs with short messages
Quantum Physics · Submitted 3 Apr 2010
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We prove that in all of these cases the short messages can be eliminated without changing the power of the model, so the first variant has the expressive power of QMA and the second and third variants have the expressive power of BQP.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
This paper considers three variants of quantum interactive proof systems in which short (meaning logarithmic-length) messages are exchanged between the prover and verifier. The first variant is one in which the verifier sends a short message to the prover, and the prover responds with an ordinary, or polynomial-length, message; the second variant is one in which any number of messages can be exchanged, but where the combined length of all the messages is logarithmic; and the third variant is one in which the verifier sends polynomially many random bits to the prover, who responds with a short quantum message. We prove that in all of these cases the short messages can be eliminated without changing the power of the model, so the first variant has the expressive power of QMA and the second and third variants have the expressive power of BQP. These facts are proved through the use of quantum state tomography, along with the finite quantum de Finetti theorem for the first variant.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | This paper considers three variants of quantum interactive proof systems in which short (meaning logarithmic-length) messages are exchanged between the prover and verifier. | background 0.56 | 0.56 | 0.03 | asserted 0.92 |
| s1 | The first variant is one in which the verifier sends a short message to the prover, and the prover responds with an ordinary, or polynomial-length, message; the second variant is one in which any number of messages can be exchanged, but where the combined length of all the messages is logarithmic; and the third variant is one in which the verifier sends polynomially many random bits to the prover, who responds with a short quantum message. | contribution 0.60 | 0.16 | 0.03 | asserted 0.89 |
| s2 | We prove that in all of these cases the short messages can be eliminated without changing the power of the model, so the first variant has the expressive power of QMA and the second and third variants have the expressive power of BQP. | result 0.99 | 0.95 | 0.93 | asserted 1.00 |
| s3 | These facts are proved through the use of quantum state tomography, along with the finite quantum de Finetti theorem for the first variant. | method 1.00 | 0.86 | 0.03 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
This paper considers three variants of quantum interactive proof systems in which short (meaning logarithmic-length) messages are exchanged between the prover and verifier. The first variant is one in which the verifier sends a short message to the prover, and the prover responds with an ordinary, or polynomial-length, message; the second variant is one in which any number of messages can be exchanged, but where the combined length of all the messages is logarithmic; and the third variant is one in which the verifier sends polynomially many random bits to the prover, who responds with a short quantum message. We prove that in all of these cases the short messages can be eliminated without changing the power of the model, so the first variant has the expressive power of QMA and the second and third variants have the expressive power of BQP. These facts are proved through the use of quantum state tomography, along with the finite quantum de Finetti theorem for the first variant.
Human review
References
How the literature uses it
5 arXiv papers cite this in 8 sentences
Papers citing it · 3 sentences without a confident label
Contests it 1 paper
-
Note that the known $n12/31/3 =$ proofs [ref] break down if the gap is so small.
Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap · More Open Problems · contest 0.78
Uses its method or tool 2 papers
-
However, by using the techniques from the recent result [ref] , we can prove the product-QRG(2) contains all the languages which can recognized by the most general model of one-round quantum refereed game except the message sent to Yes prover is only of poly-logarithm size.
Parallelized Solution to Semidefinite Programmings in Quantum Complexity Theory · One-round Product QRG · 0.93
-
To see that the mathematical notion of exact sequential simulation implies the physical one, we use the method of post-selected teleportation, essentially the same idea as what was used in the proof of [ref] .
Exact entanglement cost of quantum states and channels under PPT-preserving operations · Physical justification for definition of exact sequential channel simulation · 0.98
Cites it as background 2 papers
-
Variants of time-bounded quantum interactive proofs with short messages were explored in [ref] .
Space-bounded quantum interactive proof systems · Related works · 0.97
-
For example one can consider the case where some or all of the messages are short, meaning at most logarithmic in the input length [ref] .
Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap · Introduction · 0.96
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.