EUVIMEDEUVIMED entdecken
Crossref

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits

Alex Grilo, Elham Kashefi, Damian Markham, Michael Oliveira

ACM Transactions on Quantum Computing · 18.05.2026

DOI: 10.1145/3802819 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Quantum Computing, online erschienen am 18.05.2026. Verfasst von Alex Grilo und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 48 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The relevance of shallow-depth quantum circuits has recently increased, mainly due to their applicability to near-term devices. In this context, one of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. Our first contribution in this work is to prove new separations between classical and quantum constant-depth circuits. Firstly, we show a separation between constant-depth quantum circuits with quantum advice \(\mathsf {QNC}^0/\mathsf {qpoly} \) , and \(\mathsf {AC}^0[p] \) , which is the class of classical constant-depth circuits with unbounded-fan in and \(\mathsf {MOD}_{p} \) gates. Additionally, we show a separation between \(\mathsf {QAC}^0 \) , the circuit class containing Toffoli gates with unbounded control, and \(\mathsf {AC}^0[p] \) , when \(\mathsf {QAC}^0 \) is augmented with additional mid-circuit measurements and classical fanout. This establishes the first such separation for a shallow-depth quantum class that does not involve quantum fanout gates, while relying solely on finite quantum gate sets. Equivalently, this yields a separation between \(\mathsf {AC}^0[p] \) and \([\mathsf {QNC}^0, \mathsf {AC}^0]^2 \) , i.e., shallow quantum circuits interleaved with simple classical computation. Secondly, we consider \(\mathsf {QNC}^0 \) circuits with infinite-size gate sets. We show that these circuits, along with quantum prime modular gates or classical prime modular gates in combination with classical fanout, can implement threshold gates, showing that \(\mathsf {QNC}^0[p]=\mathsf {QTC}^0 \) . Finally, we also show that in the infinite-size gate set case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.

Zitieren

APA

Grilo, A., Kashefi, E., Markham, D., & Oliveira, M. (2026). The Power of Shallow-depth Toffoli and Qudit Quantum Circuits. ACM Transactions on Quantum Computing. https://doi.org/10.1145/3802819

Vancouver

Grilo A, Kashefi E, Markham D, Oliveira M. The Power of Shallow-depth Toffoli and Qudit Quantum Circuits. ACM Transactions on Quantum Computing. 2026. doi:10.1145/3802819

BibTeX
@article{Grilo2026,
  author = {Grilo, Alex and Kashefi, Elham and Markham, Damian and Oliveira, Michael},
  title = {The Power of Shallow-depth Toffoli and Qudit Quantum Circuits},
  journal = {ACM Transactions on Quantum Computing},
  year = {2026},
  doi = {10.1145/3802819}
}
Kostenlos starten →