# Classical verification of quantum circuits containing few basis changes

arXiv: https://arxiv.org/abs/1612.04914 · HTML: https://mlsanity.com/paper/1612.04914/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2016.

## Built on by (most cited first, 2 of 2)

- [Detecting Clouds in Multispectral Satellite Images Using Quantum-Kernel Support Vector Machines](https://mlsanity.com/paper/2302.08270/) (2023)
- [Cloud Detection in Multispectral Satellite Images Using Support Vector Machines With Quantum Kernels](https://mlsanity.com/paper/2307.07281/) (2023)

## Abstract (arXiv)

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.