Clifford Strategies in Interactive Protocols are Classically Simulatable
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908515859169280 |
|---|---|
| author | Shalit, Itay |
| author_facet | Shalit, Itay |
| contents | $\text{MIP}^\ast$ is the class of languages decidable by an efficient classical verifier interacting with multiple quantum provers that share entangled qubits but cannot communicate. Notably, $\text{MIP}^\ast$ was proved to equal $\text{RE}$, the class of all recursively enumerable languages.
We introduce the complexity class $\text{Clifford-MIP}^\ast$, which restricts quantum provers to Clifford operations and classical post-processing of measurement results, while still allowing shared entangled qubits in any quantum state. We show that any strategy in this model can be simulated by classical provers with shared random bits, and therefore admits a local hidden-variable description. Consequently, $\text{Clifford-MIP}^\ast = \text{MIP}$, a vastly smaller complexity class compared to $\text{RE}$.
Moreover, we resolve an open question posed by Kalai et al. (STOC 2023), by showing that quantum advantage in any single-round non-local game requires at least two provers operating outside the $\text{Clifford-MIP}^\ast$ computational model. This rules out a proposed approach for significantly improving the efficiency of quantum advantage tests that are based on compiling non-local games into single-prover interactive protocols. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12030 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Clifford Strategies in Interactive Protocols are Classically Simulatable Shalit, Itay Quantum Physics Computational Complexity Cryptography and Security $\text{MIP}^\ast$ is the class of languages decidable by an efficient classical verifier interacting with multiple quantum provers that share entangled qubits but cannot communicate. Notably, $\text{MIP}^\ast$ was proved to equal $\text{RE}$, the class of all recursively enumerable languages. We introduce the complexity class $\text{Clifford-MIP}^\ast$, which restricts quantum provers to Clifford operations and classical post-processing of measurement results, while still allowing shared entangled qubits in any quantum state. We show that any strategy in this model can be simulated by classical provers with shared random bits, and therefore admits a local hidden-variable description. Consequently, $\text{Clifford-MIP}^\ast = \text{MIP}$, a vastly smaller complexity class compared to $\text{RE}$. Moreover, we resolve an open question posed by Kalai et al. (STOC 2023), by showing that quantum advantage in any single-round non-local game requires at least two provers operating outside the $\text{Clifford-MIP}^\ast$ computational model. This rules out a proposed approach for significantly improving the efficiency of quantum advantage tests that are based on compiling non-local games into single-prover interactive protocols. |
| title | Clifford Strategies in Interactive Protocols are Classically Simulatable |
| topic | Quantum Physics Computational Complexity Cryptography and Security |
| url | https://arxiv.org/abs/2410.12030 |