The Library
Quantum proofs of proximity
Tools
Tools
Tools
Dall'Agnol, Marcel, Gur, Tom, Moulik, Subhayan Roy and Thaler, Justin (2022) Quantum proofs of proximity. Quantum, 6 . 834. doi:10.22331/q-2022-10-13-834
|
PDF
WRAP-Quantum-proofs-proximity-22.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1173Kb) | Preview |
|
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
dcs-010922-wrap--2105.03697.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (547Kb) |
Official URL: https://doi.org/10.22331/q-2022-10-13-834
Abstract
We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity
(QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property Π and reject inputs that are ε-far from Π, while only probing a minuscule portion of their input.
We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016).
Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable. A consequence of this framework is a QMA algorithm to verify the Parity of an n-bit string with
O(n2/3) queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.
| Item Type: | Journal Article | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QC Physics |
||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Quantum computing , Quantum theory , Computational complexity , Combinatorial optimization | ||||||||||||||||||
| Journal or Publication Title: | Quantum | ||||||||||||||||||
| Publisher: | Verein zur Foerderung des Open Access Publizierens in den Quantenwissenschaften | ||||||||||||||||||
| ISBN: | 2521-327X | ||||||||||||||||||
| Official Date: | 13 October 2022 | ||||||||||||||||||
| Dates: |
|
||||||||||||||||||
| Volume: | 6 | ||||||||||||||||||
| Article Number: | 834 | ||||||||||||||||||
| DOI: | 10.22331/q-2022-10-13-834 | ||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||||||||
| Date of first compliant deposit: | 2 September 2022 | ||||||||||||||||||
| Date of first compliant Open Access: | 1 November 2022 | ||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||
| Related URLs: | |||||||||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
