REVIEW 3 cited by
Quantum advantage with shallow circuits
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Quantum advantage with shallow circuits
read the original abstract
We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem which we call the 2D Hidden Linear Function problem. An instance of the problem is specified by a quadratic form q that maps n-bit strings to integers modulo four. The goal is to identify a linear boolean function which describes the action of q on a certain subset of n-bit strings. We prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the 2D Hidden Linear Function problem with high probability must have depth logarithmic in n. In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates acting locally on a two-dimensional grid.
Forward citations
Cited by 3 Pith papers
-
Genuine Global Kochen-Specker Contextuality as Classical Coordination Cost
Genuine global KS contextuality is framed as the classical coordination cost needed to maintain a global noncontextual explanation from locally available information in multipartite systems.
-
All pure entangled states can lead to fully nonlocal correlations
Non-maximally entangled states exhibit full nonlocality under simple Schmidt coefficient conditions, and all pure entangled states can be activated to full nonlocality with multiple copies.
-
Dissipative Quantum Multiplicative Weights with Sampling Feedback: A Classically Hard Primitive Realized via Engineered Open-System Dynamics
DQMW-Sample realizes a classically hard online learning primitive via dissipative quantum dynamics with sublinear regret and proven hardness for classical simulation including PH collapse.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.