Unconditional advantage of noisy qudit quantum circuits over biased threshold circuits in constant depth

Michael Oliveira (), Sathyawageeswar Subramanian (), Leandro Mendes and Min-Hsiu Hsieh ()
Additional contact information
Michael Oliveira: Hon Hai (Foxconn) Quantum Computing Research Center
Sathyawageeswar Subramanian: University of Cambridge
Leandro Mendes: Hon Hai (Foxconn) Quantum Computing Research Center
Min-Hsiu Hsieh: Hon Hai (Foxconn) Quantum Computing Research Center

Nature Communications, 2025, vol. 16, issue 1, 1-13

Abstract: 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.

Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/s41467-025-58545-4 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:16:y:2025:i:1:d:10.1038_s41467-025-58545-4

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/s41467-025-58545-4

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().