Our paper: arXiv:2609.40100
Authors: Natansh Mathur, Iordanis Kerenidis (Quantum Signals)
Sampling problems are among the clearest places where quantum computers are expected to do something classical computers cannot. This paper shows that one such problem, Fermion Sampling, keeps its hardness guarantees with circuits far shallower than previously required.
Why we wrote it
The known hardness results for Fermion Sampling assumed fully random transformations, which need circuit depth that grows linearly with the number of qubits and a quadratic number of gates. That depth is a problem on today's hardware, where every extra layer adds noise. We wanted to know whether the guarantees survive with shallow circuits that real machines can run.
How it fits our work
Our quantum research explores a design in which a trained fermionic circuit acts as a sampler and a classical model reads its samples. The value of that design rests on the samples being hard to reproduce classically. This paper shows the hardness holds at logarithmic depth, which makes the sampler a realistic target for near-term quantum computers rather than only for future fault-tolerant ones.
What it adds to our approach
- Anticoncentration at log depth. Output probabilities spread out like those of a fully random circuit after a sharp threshold of about 0.855 log2 n layers.
- Average-case hardness at log depth. Estimating output probabilities is #P-hard on most instances, with O(n log n) gates.
- The input matters. The non-Gaussian magic input is what makes shallow circuits sufficient; a plain occupation-basis input does not reach the same scale.
- Hardware-native. A finite set of 192 gates preserves the result exactly, which keeps the construction implementable.
Key takeaway
Depth falls from linear to logarithmic in the number of modes: for 1,024 modes, the anticoncentration threshold is about 9 layers rather than a depth that grows with all 1,024. The gate budget drops from order n² to order n log n, roughly a hundredfold fewer gates at that size before constants. Sampling from our shallow fermionic circuits is now provably hard (in the same sense as boson sampling and random circuit sampling).
Read the full paper on arXiv. For questions about our research, contact info[at]quantumsignals.ai.