A game of quantum advantage: linking verification and simulation

Research output: Contribution to journalJournal articlepeer-review

Standard

A game of quantum advantage : linking verification and simulation. / França, Daniel Stilck; Garcia-Patron, Raul.

In: Quantum, Vol. 6, 753, 2022, p. 1-44.

Research output: Contribution to journalJournal articlepeer-review

Harvard

França, DS & Garcia-Patron, R 2022, 'A game of quantum advantage: linking verification and simulation', Quantum, vol. 6, 753, pp. 1-44. https://doi.org/10.22331/Q-2022-06-30-753

APA

França, D. S., & Garcia-Patron, R. (2022). A game of quantum advantage: linking verification and simulation. Quantum, 6, 1-44. [753]. https://doi.org/10.22331/Q-2022-06-30-753

Vancouver

França DS, Garcia-Patron R. A game of quantum advantage: linking verification and simulation. Quantum. 2022;6:1-44. 753. https://doi.org/10.22331/Q-2022-06-30-753

Author

França, Daniel Stilck ; Garcia-Patron, Raul. / A game of quantum advantage : linking verification and simulation. In: Quantum. 2022 ; Vol. 6. pp. 1-44.

Bibtex

@article{c56687b4a36d41729983dfa46c78bd85,
title = "A game of quantum advantage: linking verification and simulation",
abstract = "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. The model captures most of the currently existing quantum advantage verification techniques. In this formalism, Bob samples from a 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. Bob 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. Finally, 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.",
author = "Fran{\c c}a, {Daniel Stilck} and Raul Garcia-Patron",
note = "Publisher Copyright: {\textcopyright} 2022 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. All right reserved.",
year = "2022",
doi = "10.22331/Q-2022-06-30-753",
language = "English",
volume = "6",
pages = "1--44",
journal = "Quantum",
issn = "2521-327X",
publisher = "Verein zur F{\"o}rderung des Open Access Publizierens in den Quantenwissenschaften",

}

RIS

TY - JOUR

T1 - A game of quantum advantage

T2 - linking verification and simulation

AU - França, Daniel Stilck

AU - Garcia-Patron, Raul

N1 - Publisher Copyright: © 2022 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. All right reserved.

PY - 2022

Y1 - 2022

N2 - 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. The model captures most of the currently existing quantum advantage verification techniques. In this formalism, Bob samples from a 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. Bob 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. Finally, 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.

AB - 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. The model captures most of the currently existing quantum advantage verification techniques. In this formalism, Bob samples from a 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. Bob 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. Finally, 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.

UR - http://www.scopus.com/inward/record.url?scp=85134568524&partnerID=8YFLogxK

U2 - 10.22331/Q-2022-06-30-753

DO - 10.22331/Q-2022-06-30-753

M3 - Journal article

AN - SCOPUS:85134568524

VL - 6

SP - 1

EP - 44

JO - Quantum

JF - Quantum

SN - 2521-327X

M1 - 753

ER -

ID: 318813130