Depth-efficient proofs of quantumness
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify the $\textit{quantum advantage}$ of an untrusted prover. That is, a quantum prover can correctly answer the verifier's challenges and be accepted, while any polynomial-time clas...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2022-09-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2022-09-19-807/pdf/ |
| _version_ | 1797995303968702464 |
|---|---|
| author | Zhenning Liu Alexandru Gheorghiu |
| author_facet | Zhenning Liu Alexandru Gheorghiu |
| author_sort | Zhenning Liu |
| collection | DOAJ |
| description | A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify the $\textit{quantum advantage}$ of an untrusted prover. That is, a quantum prover can correctly answer the verifier's challenges and be accepted, while any polynomial-time classical prover will be rejected with high probability, based on plausible computational assumptions. To answer the verifier's challenges, existing proofs of quantumness typically require the quantum prover to perform a combination of polynomial-size quantum circuits and measurements.
In this paper, we give two proof of quantumness constructions in which the prover need only perform $\textit{constant-depth quantum circuits}$ (and measurements) together with log-depth classical computation. Our first construction is a generic compiler that allows us to translate all existing proofs of quantumness into constant quantum depth versions. Our second construction is based around the $\textit{learning with rounding}$ problem, and yields circuits with shorter depth and requiring fewer qubits than the generic construction. In addition, the second construction also has some robustness against noise. |
| first_indexed | 2024-04-11T09:59:37Z |
| format | Article |
| id | doaj.art-7dadaeee550941f2a24424892b2aae58 |
| institution | Directory Open Access Journal |
| issn | 2521-327X |
| language | English |
| last_indexed | 2024-04-11T09:59:37Z |
| publishDate | 2022-09-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj.art-7dadaeee550941f2a24424892b2aae582022-12-22T04:30:27ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2022-09-01680710.22331/q-2022-09-19-80710.22331/q-2022-09-19-807Depth-efficient proofs of quantumnessZhenning LiuAlexandru GheorghiuA proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify the $\textit{quantum advantage}$ of an untrusted prover. That is, a quantum prover can correctly answer the verifier's challenges and be accepted, while any polynomial-time classical prover will be rejected with high probability, based on plausible computational assumptions. To answer the verifier's challenges, existing proofs of quantumness typically require the quantum prover to perform a combination of polynomial-size quantum circuits and measurements. In this paper, we give two proof of quantumness constructions in which the prover need only perform $\textit{constant-depth quantum circuits}$ (and measurements) together with log-depth classical computation. Our first construction is a generic compiler that allows us to translate all existing proofs of quantumness into constant quantum depth versions. Our second construction is based around the $\textit{learning with rounding}$ problem, and yields circuits with shorter depth and requiring fewer qubits than the generic construction. In addition, the second construction also has some robustness against noise.https://quantum-journal.org/papers/q-2022-09-19-807/pdf/ |
| spellingShingle | Zhenning Liu Alexandru Gheorghiu Depth-efficient proofs of quantumness Quantum |
| title | Depth-efficient proofs of quantumness |
| title_full | Depth-efficient proofs of quantumness |
| title_fullStr | Depth-efficient proofs of quantumness |
| title_full_unstemmed | Depth-efficient proofs of quantumness |
| title_short | Depth-efficient proofs of quantumness |
| title_sort | depth efficient proofs of quantumness |
| url | https://quantum-journal.org/papers/q-2022-09-19-807/pdf/ |
| work_keys_str_mv | AT zhenningliu depthefficientproofsofquantumness AT alexandrugheorghiu depthefficientproofsofquantumness |