Simulating the quantum switch with quantum circuits is computationally hard
Higher-order transformations acting on input quantum channels in an indefinite causal order-such as the quantum switch-cannot be described by quantum circuits using the same number of calls to the input channels. A natural question is whether they can be simulated, i.e., whether their action can be exactly and deterministically reproduced by a quantum circuit with more calls to the input channels. Here, we prove that the quantum switch acting on two n-qubit channels cannot be simulated by any quantum circuit using k calls to one channel and one to the other, if k < 2<sup>n</sup>. This establishes an exponential separation in quantum query complexity between processes with indefinite causal order and quantum circuits. Moreover, even with one extra call to both input channels, such a simulation remains impossible. We further demonstrate the robustness of this separation by extending the result to probabilistic and approximate simulations scenarios.
Authors
- Philip Taranto (ORCID: https://orcid.org/0000-0002-4247-3901)
- Hlér Kristjánsson (ORCID: https://orcid.org/0000-0003-4465-2863)
- Jessica Bavaresco (ORCID: https://orcid.org/0000-0002-4823-0353)
- Tatsuki Odake (ORCID: https://orcid.org/0009-0009-6844-9959)
- Satoshi Yoshida (ORCID: https://orcid.org/0000-0002-0521-5209)
- Marco Túlio Quintino (ORCID: https://orcid.org/0000-0003-1332-3477)
- Mio Murao (ORCID: https://orcid.org/0000-0001-7861-1774)
Institutions
- University of Geneva (CH)
- Centre National de la Recherche Scientifique (FR)
- University of Waterloo (CA)
- Perimeter Institute (CA)
- Université Paris Cité (FR)
- University of Manchester (GB)
- Sorbonne Université (FR)
- LIP6 (FR)
- Université de Montréal (CA)
- The University of Tokyo (JP)
Publication Details
- Journal
- Nature Communications
- Published
- 2025-11-20
- DOI
- https://doi.org/10.1038/s41467-025-64996-6
- Citations
- 1
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- article
- Field-Weighted Citation Impact
- 2.48
Funders
- National Science Foundation
- National Centres of Competence in Research SwissMAP
- Government of Canada
- Ministry of Education, Culture, Sports, Science and Technology
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
- Institut Périmètre de physique théorique
- Ministry of Colleges and Universities
- Japan Society for the Promotion of Science