Journal article
Unconditional advantage of noisy qudit quantum circuits over biased threshold circuits in constant depth
- Abstract:
- The rapid evolution of quantum devices fuels concerted efforts to experimentally establish quantum advantage over classical computing. Many demonstrations of quantum advantage, however, rely on computational assumptions and face verification challenges. Furthermore, steady advances in classical algorithms and machine learning make the issue of provable, practically demonstrable quantum advantage a moving target. In this work, we unconditionally demonstrate that parallel quantum computation can exhibit greater computational power than previously recognized. We prove that polynomial-size biased threshold circuits of constant depth—which model neural networks with tunable expressivity—fail to solve certain problems solvable by small constant-depth quantum circuits with local gates, for values of the bias that allow quantifiably large computational power. Additionally, we identify a family of problems that are solvable in constant depth by a universal quantum computer over prime-dimensional qudits with bounded connectivity, but remain hard for polynomial-size biased threshold circuits. We thereby bridge the foundational theory of non-local games in higher dimensions with computational advantage on emerging devices operating on a wide range of physical platforms. Finally, we show that these quantum advantages are robust to noise across all prime qudit dimensions with all-to-all connectivity, enhancing their practical appeal
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 918.2KB, Terms of use)
-
- Publisher copy:
- 10.1038/s41467-025-58545-4
Authors
- Publisher:
- Nature Research
- Journal:
- Nature Communications More from this journal
- Volume:
- 16
- Issue:
- 1
- Pages:
- 3559-3559
- Article number:
- 3559
- Publication date:
- 2025-04-15
- DOI:
- EISSN:
-
2041-1723
- ISSN:
-
2041-1723
- Language:
-
English
- Keywords:
- Pubs id:
-
2366638
- Local pid:
-
pubs:2366638
- Source identifiers:
-
W4409466895
- Deposit date:
-
2026-02-04
- ARK identifier:
This ORA record was generated from metadata provided by an external service. It has not been edited by the ORA Team.
Terms of use
- Copyright date:
- 2025
If you are the owner of this record, you can report an update to it here: Report update to this record