Classical verification of quantum circuits containing few basis changes

Tommaso F. Demarie, Yingkai Ouyang, and Joseph F. Fitzsimons
Phys. Rev. A 97, 042319 – Published 11 April 2018

Abstract

We consider the task of verifying the correctness of quantum computation for a restricted class of circuits which contain at most two basis changes. This contains circuits giving rise to the second level of the Fourier hierarchy, the lowest level for which there is an established quantum advantage. We show that when the circuit has an outcome with probability at least the inverse of some polynomial in the circuit size, the outcome can be checked in polynomial time with bounded error by a completely classical verifier. This verification procedure is based on random sampling of computational paths and is only possible given knowledge of the likely outcome.

  • Received 1 June 2017

DOI:https://doi.org/10.1103/PhysRevA.97.042319

©2018 American Physical Society

Physics Subject Headings (PhySH)

  1. Research Areas
Quantum Information, Science & Technology

Authors & Affiliations

Tommaso F. Demarie*, Yingkai Ouyang, and Joseph F. Fitzsimons

  • Singapore University of Technology and Design, 8 Somapah Road, Singapore 487372 and Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543

  • *tommaso_demarie@sutd.edu.sg
  • yingkai_ouyang@sutd.edu.sg
  • joseph_fitzsimons@sutd.edu.sg

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 97, Iss. 4 — April 2018

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×