This record is in review state, the data has not yet been validated.
This is not the latest version of this item. The latest version can be found here.
Peaked quantum advantage using error correction
Loading...
Author / Producer
Date
2025-10-06
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
Data
Rights / License
Abstract
A key issue of current quantum advantage experiments is that their verification requires a full classical simulation of the ideal computation. This limits the regime in which the experiments can be verified to precisely the regime in which they are also simulatable. An important outstanding question is therefore to find quantum advantage schemes that are also classically verifiable. We make progress on this question by designing a new quantum advantage proposal--Hidden Code Sampling--whose output distribution is conditionally peaked. These peaks enable verification in far less time than it takes for full simulation. At the same time, we show that exactly sampling from the output distribution is classically hard unless the polynomial hierarchy collapses, and we propose a plausible conjecture regarding average-case hardness. Our scheme is based on ideas from quantum error correction. The required quantum computations are closely related to quantum fault-tolerant circuits and can potentially be implemented transversally. Our proposal may thus give rise to a next generation of quantum advantage experiments en route to full quantum fault tolerance.
Permanent link
Publication status
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
Publisher
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03781 - Renner, Renato / Renner, Renato