A game of quantum advantage: linking verification and simulation
We present a formalism that captures the process of proving quantum superiority to skeptics as an interactive game between two agents, supervised by a referee. Bob, is sampling from a classical distribution on a quantum device that is supposed to demonstrate a quantum advantage. The other player, th...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2022-06-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2022-06-30-753/pdf/ |
| _version_ | 1811237581022560256 |
|---|---|
| author | Daniel Stilck França Raul Garcia-Patron |
| author_facet | Daniel Stilck França Raul Garcia-Patron |
| author_sort | Daniel Stilck França |
| collection | DOAJ |
| description | We present a formalism that captures the process of proving quantum superiority to skeptics as an interactive game between two agents, supervised by a referee. Bob, is sampling from a classical distribution on a quantum device that is supposed to demonstrate a quantum advantage. The other player, the skeptical Alice, is then allowed to propose mock distributions supposed to reproduce Bob's device's statistics. He then needs to provide witness functions to prove that Alice's proposed mock distributions cannot properly approximate his device. Within this framework, we establish three results. First, for random quantum circuits, Bob being able to efficiently distinguish his distribution from Alice's implies efficient approximate simulation of the distribution. Secondly, finding a polynomial time function to distinguish the output of random circuits from the uniform distribution can also spoof the heavy output generation problem in polynomial time. This pinpoints that exponential resources may be unavoidable for even the most basic verification tasks in the setting of random quantum circuits. Beyond this setting, by employing strong data processing inequalities, our framework allows us to analyse the effect of noise on classical simulability and verification of more general near-term quantum advantage proposals. |
| first_indexed | 2024-04-12T12:26:00Z |
| format | Article |
| id | doaj.art-f21eeee17c444092beec18d4527742c6 |
| institution | Directory Open Access Journal |
| issn | 2521-327X |
| language | English |
| last_indexed | 2024-04-12T12:26:00Z |
| publishDate | 2022-06-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj.art-f21eeee17c444092beec18d4527742c62022-12-22T03:33:10ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2022-06-01675310.22331/q-2022-06-30-75310.22331/q-2022-06-30-753A game of quantum advantage: linking verification and simulationDaniel Stilck FrançaRaul Garcia-PatronWe present a formalism that captures the process of proving quantum superiority to skeptics as an interactive game between two agents, supervised by a referee. Bob, is sampling from a classical distribution on a quantum device that is supposed to demonstrate a quantum advantage. The other player, the skeptical Alice, is then allowed to propose mock distributions supposed to reproduce Bob's device's statistics. He then needs to provide witness functions to prove that Alice's proposed mock distributions cannot properly approximate his device. Within this framework, we establish three results. First, for random quantum circuits, Bob being able to efficiently distinguish his distribution from Alice's implies efficient approximate simulation of the distribution. Secondly, finding a polynomial time function to distinguish the output of random circuits from the uniform distribution can also spoof the heavy output generation problem in polynomial time. This pinpoints that exponential resources may be unavoidable for even the most basic verification tasks in the setting of random quantum circuits. Beyond this setting, by employing strong data processing inequalities, our framework allows us to analyse the effect of noise on classical simulability and verification of more general near-term quantum advantage proposals.https://quantum-journal.org/papers/q-2022-06-30-753/pdf/ |
| spellingShingle | Daniel Stilck França Raul Garcia-Patron A game of quantum advantage: linking verification and simulation Quantum |
| title | A game of quantum advantage: linking verification and simulation |
| title_full | A game of quantum advantage: linking verification and simulation |
| title_fullStr | A game of quantum advantage: linking verification and simulation |
| title_full_unstemmed | A game of quantum advantage: linking verification and simulation |
| title_short | A game of quantum advantage: linking verification and simulation |
| title_sort | game of quantum advantage linking verification and simulation |
| url | https://quantum-journal.org/papers/q-2022-06-30-753/pdf/ |
| work_keys_str_mv | AT danielstilckfranca agameofquantumadvantagelinkingverificationandsimulation AT raulgarciapatron agameofquantumadvantagelinkingverificationandsimulation AT danielstilckfranca gameofquantumadvantagelinkingverificationandsimulation AT raulgarciapatron gameofquantumadvantagelinkingverificationandsimulation |