Journal
PHYSICAL REVIEW A
Volume 97, Issue 4, Pages -Publisher
AMER PHYSICAL SOC
DOI: 10.1103/PhysRevA.97.042319
Keywords
-
Categories
Funding
- Singapore's National Research Foundation
- Air Force Office of Scientific Research under AOARD [FA2386-15-1-4082]
- Singapore National Research Foundation under NRF [NRF-NRFF2013-01]
- Ministry of Education
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available