betaFeedback

WorksPhysics and Astronomy

Efficient quantum-circuit simulation of classical control of computational order

Abstract

We show that quantum circuits with classical control of computational order admit an efficient simulation by fixed-order quantum circuits: any such transformation acting on NN independent quantum channels can be deterministically, exactly, and universally simulated using at most N2N^2 queries. We generalize these constructions to extended, bipartite quantum channels and quantum instruments, and demonstrate that they can be implemented catalytically, without consuming the additional N2−NN^2-N queries required for the simulation. In the case of quantum circuits with quantum control of computational order, we prove a similar simulation result, but restricted to unitary input channels (hence non-universal). These results show the limitations of the computational power of these classes of transformations in the studied scenarios.

The quantum circuit model is one of the most widely applied models of quantum computing. A well-known such example is the quantum circuit that implements Shor’s algorithm, a paramount result in quantum computing about the efficient factoring of integer numbers [1]. Quantum channels are central to this framework: traditionally regarded as devices transporting, and in the process, transforming quantum states—such as in communication tasks—they are also key characters of quantum circuits, which are composed of a sequence of quantum gates and measurements. The more recent formalism of higher-order quantum computing [2, 3, 4, 5] places quantum channels center stage, not only as the means to execute a computation through a quantum circuit, but as the input and output of the computation itself.

Formally, a higher-order transformation called a superchannel is the most general linear map that transforms several quantum channels into another quantum channel [2, 3, 4, 6]. Hence, a quantum circuit with open slots, where arbitrary quantum channels can be plugged in, can be seen as a higher-order transformation. Since quantum channels carry an inherent input–output structure, the question of causal order naturally emerges when transforming multiple channels. Strikingly, this formalism allows superchannels that act on the input channels in a manner that goes beyond what can be described with the standard paradigm of quantum circuits, where quantum gates are implemented on a fixed, pre-defined order. These transformations play with the order in which the input channels are acted upon: they can be described with classical control of computational order [7, 8] or even with quantum control of computational order [7, 8], leading to computations that can be understood as carried out in a dynamical and/or in an indefinite causal order [8, 9, 10, 11]. Such transformations raise immediate fundamental questions about the role of causality in quantum theory, as well as more practical questions, concerning their implementability and potential advantages.

Theoretical advantages of quantum control of computational order have been confirmed in a wide range of quantum information processing tasks, such as quantum channel discrimination [12, 13, 14], quantum metrology [15, 16, 17], quantum computational and query complexity [18, 19], among others. As for classical control, a so far less explored class of transformations, an advantage has been recently reported [20] with respect to fixed-order strategies in a task of approximately simulating quantum control of computational order, and another was obtained with respect to convex mixtures of fixed-order strategies in a causal game [11]. Such information-processing advantages have mostly been shown via comparison with fixed-order quantum circuits that act on a single call of each input channel. However, their true practical significance depends on whether these advantages would still hold when comparing superchannels with quantum and classical control of computational order against fixed-order quantum circuits that use a larger number of queries to the input channels. Recent results have shown that a universal, deterministic, and exact simulation of the quantum switch, a superchannel with quantum control of computational order, is at least computationally hard, if at all possible [20].

In contrast, in this work, we show that classical control of computational order can be simulated in a quantum query-efficient manner: we prove that any quantum circuit with classical control of computational order that acts on NN independent quantum channels can be deterministically, exactly, and universally simulated by a fixed-order quantum circuit that acts on at most N2N^2 queries to the input quantum channels. Our proof is constructive and builds on top of a known quantum circuit that can simulate the action of the quantum NN-switch on unitary channels [18, 21, 22]. We generalize these results to show that, at no extra cost in terms of channel queries, these simulations can be adapted to work for extended quantum channels and quantum instruments, and can furthermore be made catalytically, i.e., without consuming the N2−NN^2-N extra queries of the input channels. Moreover, we show that quantum circuits with quantum control of computational order can also be simulated in a

Table 1.

similar manner, albeit not universally: their action on NN unitary quantum channels can be deterministically and exactly simulated with at most N2N^2 queries to the input unitary channels. Such simulations can also be generalized to extended unitary channels and be made catalytically, similarly to the classical control case. Beyond establishing efficient simulations, these results help to clarify the computational power in terms of quantum query complexity of the largest currently known physically interpretable classes of higher-order transformations.

—Quantum channels and superchannels. In quantum theory, quantum channels are deterministic transformations of quantum states, described by completely positive, trace-preserving (CPTP) linear maps A:L(HI)→L(HO)\mathcal{A}: \mathcal{L}(\mathcal{H}_{I}) \to\mathcal{L}(\mathcal{H}_{O}) that map all quantum states ρ∈L(HI⊗HI′)\rho\in\mathcal{L}(\mathcal{H}_{I} \otimes\mathcal{H}_{I'}) acting on a joint input and auxiliary Hilbert space to quantum states A⊗I(ρ)∈L(HO⊗HI′)\mathcal{A} \otimes\mathcal{I}(\rho) \in\mathcal{L}(\mathcal{H}_{O} \otimes\mathcal{H}_{I'}) acting on a joint output and auxiliary Hilbert space, where I\mathcal{I} is the identity map on the auxiliary system, even when acting only on part of the input state. Unitary channels U(ρ)=UρU†\mathcal{U}(\rho)=U\rho U^\dagger, characterized by unitary operators U:HI→HOU:\mathcal{H}_{I}\to\mathcal{H}_{O}, HI≅HO\mathcal{H}_{I}\cong\mathcal{H}_{O}, satisfying U†U=1U^\dagger U=1, are a particular case of quantum channel.

Superchannels, on the other hand, are higher-order transformations whose inputs and outputs are quantum channels themselves. That is, they are linear higher-order maps S:⨂i=1N[L(HIi)→L(HOi)]→[L(HP)→L(HF)]S:\bigotimes_{i=1}^{N}[\mathcal{L}(\mathcal{H}_{I_i})\to\mathcal{L}(\mathcal{H}_{O_i})]\to[\mathcal{L}(\mathcal{H}_{P})\to\mathcal{L}(\mathcal{H}_{F})] that act on part of NN independent quantum channels Ai:L(HIi⊗HIi′)→L(HOi⊗HOi′)\mathcal{A}_{i}:\mathcal{L}(\mathcal{H}_{I_i}\otimes\mathcal{H}_{I'_i})\to\mathcal{L}(\mathcal{H}_{O_i}\otimes\mathcal{H}_{O'_i}), where HIi′\mathcal{H}_{I'_i} and HOi′\mathcal{H}_{O'_i} are auxiliary input and output Hilbert spaces, and transform them into another channel S⊗I(A1⊗…⊗AN):L(⨂i=1NHIi⊗HP)→L(⨂i=1NHOi′⊗HF)S\otimes\mathcal{I}(\mathcal{A}_{1}\otimes\ldots\otimes\mathcal{A}_{N}):\mathcal{L}(\bigotimes_{i=1}^{N}\mathcal{H}_{I_i}\otimes\mathcal{H}_{P})\to\mathcal{L}(\bigotimes_{i=1}^{N}\mathcal{H}_{O'_i}\otimes\mathcal{H}_{F}), where I\mathcal{I} is the higher-order identity map acting on the auxiliary systems. To guarantee that the superchannels SS transform quantum channels into quantum channels, even when acting only on part of the input channels, they must correspond to completely CPTP preserving linear maps.

Superchannels have been studied in the literature of higher-order quantum operations with regards to the mathematical characterization of their Choi operators, their implementation within the quantum circuit model, and their physical and causality properties. Here, our focus is on three sets of superchannels: the set of those that can be described by quantum circuits with a fixed-order of computation (QC-FO) [2, 3, 4]; those that can be described by quantum circuits with a classical control of computational order (QC-CC), in which the order of application of each input channel is determined by the state of a classical control system [7, 8]; and finally those that can be described by quantum circuits with a quantum control of computational order (QC-QC), in which the order of application of each input channel is determined by the state of a quantum control system [7, 8]. While a precise mathematical definition of each of these sets is provided in the Appendix, here we discuss their defining physical features.

Quantum circuits with fixed computational order (QC-FO). Also known as quantum combs, these superchannels act on their input channels in a fixed and pre-defined order. They are characterized by quantum circuits with open slots, where the input channels can be plugged in, which apply intermediary gates between each input quantum channel that may act jointly on auxiliary quantum systems, often referred to as quantum memory [2, 3, 4]. Here, they will be represented by higher-order maps C∈QC-FOC\in\mathrm{QC\text{-}FO} (see Figure 1(a)). A precise definition is given in App. A2.

Figure 1. Generalized quantum circuits. Graphical representation of (a) a quantum circuit with a fixed computational order, defined by the superchannels C∈QC-FOC\in\mathrm{QC\text{-}FO}, (b) a quantum circuit with a classical control of computational order, defined by the superchannels SCC∈QC-CCS_{\mathrm{CC}}\in\mathrm{QC\text{-}CC}, and (c) a quantum circuit with a quantum control of computational order, defined by the superchannels SQC∈QC-QCS_{\mathrm{QC}}\in\mathrm{QC\text{-}QC}.

Quantum circuits with classical control of computational order (QC-CC). These superchannels are a generalization of standard quantum circuits, which act on their input channels in an order that is determined by the state of a classical control system. QC-CC superchannels have open slots, in which a single quantum channel can be plugged, however, the choice of which quantum channel will be applied in each slot is not pre-determined: the order in which the channels are called may thus be probabilistic or dynamical, but it can nevertheless be interpreted as a well-defined causal order. They apply intermediary operations that act jointly on auxiliary systems—including, in particular, on the classical control system that can be internally updated to probabilistically determine “on the fly” which input quantum channel will be acted upon next [7, 8]. QC-CC coincides with the class of causally separable superchannels [23, 24], making it the largest class of superchannels with a clear physical interpretation in terms of a definite causal order. Here, they will be represented by higher-order maps SCC∈QC-CCS_{\mathrm{CC}}\in\mathrm{QC\text{-}CC} (see Figure 1(b)). A precise definition is given in App. B1. The canonical example of a QC-CC superchannel is the classical switch [7].

Figure 2. Simulation of a superchannel. Graphical representation of different scenarios for the simulation of a superchannel SS (which may be in QC-CC or a QC-QC, but is not limited to these) that acts on N=2N=2 input quantum channels, A1\mathcal{A}_1 and A2\mathcal{A}_2, by a fixed-order quantum circuit CC, C′C', or C^∈\widehat{C} \in QC-FO that acts on more queries of the input quantum channels: (a) depicts the superchannel simulation of Def. 1, where the action of SS on all quantum channels is reproduced by CC, (b) depicts the extended superchannel simulation of Def. 2, where the action of SS on all extended quantum channels is reproduced by C′C', and (c) depicts the catalytic superchannel simulation of Def. 3, where the action on all quantum channels is reproduced by C^\widehat{C} and, furthermore, the extra queries needed in the simulation are recovered as an output of C^\widehat{C}.

Quantum circuits with quantum control of computational order (QC-QC). These superchannels are a generalization of quantum circuits with classical control, which allows for quantum control of computational order. This order may be dynamical and, moreover, it may be causally indefinite. In particular, it allows the possibility of entanglement between the state of the quantum control system and the order of application of the input quantum channels, in what can be interpreted as a superposition of different fixed orders [7, 8]. This is the largest class of superchannels that have a clear interpretation in terms of generalized quantum circuits. Here, they will be represented by higher-order maps SQC∈S_{\mathrm{QC}} \in QC-QC (see Figure 1(c)). A precise definition is given in App. C 1. The canonical example of a QC-QC superchannel is the quantum switch [7].

We remark that, while QC-FO ⊂\subset QC-CC ⊂\subset QC-QC, the set QC-QC is itself a strict subset of the set of all admissible superchannels [8].

Framework for quantum-circuit simulation of higher-order quantum computing. The main question we address is what is the cost, in terms of the necessary number of queries to the input quantum channels, of simulating the action of a given superchannel on a given set of inputs using standard quantum circuits, which constitute a universal model of quantum computation. Notice that this question is inherently different from what is typically considered as a simulation question in the literature of quantum computing: generally, one is interested in the cost of simulating a quantum computation using a classical computer. Here, on the other hand, we are interested in the cost of simulating a higher-order quantum computation using a quantum computer. For this purpose, we follow the simulation framework developed in Ref. [20]. We begin by defining a simulation of a superchannel.

Definition 1 (Simulation of a superchannel). A universal, deterministic, and exact simulation of a given superchannel S:⨂i=1N[L(HIi)→L(HOi)]→[L(HP)→L(HF)]S : \bigotimes_{i=1}^{N} [\mathcal{L}(\mathcal{H}_{I_i}) \to\mathcal{L}(\mathcal{H}_{O_i})] \to[\mathcal{L}(\mathcal{H}_P) \to\mathcal{L}(\mathcal{H}_F)] is a quantum circuit with fixed order C∈C \in QC-FO, where C:⨂i=1N[L(HIi)→L(HOi)]⊗ni→[L(HP)→L(HF)]C : \bigotimes_{i=1}^{N} [\mathcal{L}(\mathcal{H}_{I_i}) \to\mathcal{L}(\mathcal{H}_{O_i})]^{\otimes n_i} \to[\mathcal{L}(\mathcal{H}_P) \to\mathcal{L}(\mathcal{H}_F)], that acts on numbers ni∈Nn_i \in\mathbb{N} of queries to the respective quantum channels Ai\mathcal{A}_i, where Ai:L(HIi)→L(HOi)\mathcal{A}_i : \mathcal{L}(\mathcal{H}_{I_i}) \to\mathcal{L}(\mathcal{H}_{O_i}) with i∈{1,…,N}i \in\{1,\ldots,N\}, such that

C(A1⊗n1⊗⋯⊗AN⊗nN)=S(A1⊗⋯⊗AN),(1)C\left(\mathcal{A}_1^{\otimes n_1} \otimes\cdots\otimes\mathcal{A}_N^{\otimes n_N}\right)=S(\mathcal{A}_1\otimes\cdots\otimes\mathcal{A}_N), \tag*{(1)}

for all possible quantum channels A1,…,AN\mathcal{A}_1,\ldots,\mathcal{A}_N.

In all of the simulation scenarios approached here, when the action of the superchannel SS on only a subset of possible input channels can be assumed (e.g. only on unitary channels), the simulation is called non-universal.

Our first definition of simulation captures the notion of reproducing the action of a superchannel on any set of input channels, when this superchannel acts on the “entire” input channel. However, the full behavior of a superchannel is given by its action on part of input channels that act jointly on auxiliary systems, which in turn are not accessible to the superchannel. Therefore, to fully reproduce the action of a superchannel, a fixed-order quantum circuit must reproduce its action on any set of extended input channels. As shown in Ref. [20], this is the most general notion of simulation of a superchannel, which includes the simulation of its action on sets of quantum instruments—that is, on probabilistic transformations of quantum states that are described by sets of completely positive, trace-nonincreasing maps, which sum up to a trace-preserving map. In particular, sets of quantum instruments can be seen as a bipartite quantum channel in which one of the inputs and one of the outputs is a classical system, and hence, a simulation that works for extended input channels also works for input sets of quantum instruments.

Definition 2 (Extended simulation of a superchannel). A universal, deterministic, and exact simulation of a given superchannel S:⨂i=1N[L(HIi)→L(HOi)]→[L(HP)→L(HF)]S : \bigotimes_{i=1}^{N} [\mathcal{L}(\mathcal{H}_{I_i}) \to\mathcal{L}(\mathcal{H}_{O_i})] \to[\mathcal{L}(\mathcal{H}_P) \to\mathcal{L}(\mathcal{H}_F)] on extended quantum channels is a

References

  1. [1]P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proceedings 35th Annual Symposium on Foundations of Computer Science (1994) pp. 124–134.
  2. [2]G. Chiribella, G. M. D’Ariano, and P. Perinotti, Quantum circuit architecture, Phys. Rev. Lett. 101, 060401 (2008), arXiv:0712.1325 [quant-ph].
  3. [3]G. Chiribella, G. M. D’Ariano, and P. Perinotti, Theoretical framework for quantum networks, Phys. Rev. A 80, 022339 (2009), arXiv:0904.4483 [quant-ph].DOI
  4. [4]G. Chiribella, G. M. D’Ariano, and P. Perinotti, Transforming quantum operations: Quantum supermaps, EPL 83, 30004 (2008), arXiv:0804.0180 [quant-ph].DOI
  5. [5]P. Taranto, S. Milz, M. Murao, M. T. Quintino, and K. Modi, Higher-Order Quantum Operations, arXiv:2503.09693 [quant-ph] (2025).arxiv.org/abs/2503.09693
  6. [6]O. Oreshkov, F. Costa, and C. Brukner, Quantum correlations with no causal order, Nat. Commun. 3, 1092 (2012), arXiv:1105.4464 [quant-ph].DOI
  7. [7]G. Chiribella, G. M. D’Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Phys. Rev. A 88, 022318 (2013), arXiv:0912.0195 [quant-ph].
  8. [8]J. Wechs, H. Dourdent, A. A. Abbott, and C. Branciard, Quantum circuits with classical versus quantum control of causal order, PRX Quantum 2, 030335 (2021), arXiv:2101.08796 [quant-ph].DOI
  9. [9]Ä. Baumeler and S. Wolf, Perfect signaling among three parties violating predefined causal order, in 2014 IEEE International Symposium on Information Theory (2014) pp. 526–530, arXiv:1312.5916 [quant-ph].DOI
  10. [10]O. Oreshkov and C. Giarmatzi, Causal and causally separable processes, New J. Phys. 18, 093020 (2016), arXiv:1506.05449 [quant-ph].DOI
  11. [11]R. Mothe, A. A. Abbott, and C. Branciard, Correlations and quantum circuits with dynamical causal order, arXiv:2507.07992 [quant-ph] (2025).arxiv.org/abs/2507.07992
  12. [12]G. Chiribella, Perfect discrimination of no-signalling channels via quantum superposition of causal structures, Phys. Rev. A 86, 040301(R) (2012), arXiv:1109.5154 [quant-ph].DOI
  13. [13]J. Bavaresco, M. Murao, and M. T. Quintino, Strict hier- archy between parallel, sequential, and indefinite-causal-order strategies for channel discrimination, Phys. Rev. Lett. 127, 200504 (2021), arXiv:2011.08300 [quant-ph].
  14. [14]J. Bavaresco, M. Murao, and M. T. Quintino, Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies, J. Math. Phys. 63, 042203 (2022), arXiv:2105.13369 [quant-ph].DOI
  15. [15]X. Zhao, Y. Yang, and G. Chiribella, Quantum Metrology with Indefinite Causal Order, Phys. Rev. Lett. 124, 190503 (2020), arXiv:1912.02449 [quant-ph].DOI
  16. [16]Q. Liu, Z. Hu, H. Yuan, and Y. Yang, Optimal strategies for quantum metrology with a strict hierarchy, Phys. Rev. Lett. 130, 070803 (2023), arXiv:2203.09758 [quant-ph].
  17. [17]R. Mothe, C. Branciard, and A. A. Abbott, Reassessing the advantage of indefinite causal orders for quantum metrology, Phys. Rev. A 109, 062435 (2024), arXiv:2312.12172 [quant-ph].DOI
  18. [18]M. Araújo, F. Costa, and C. Brukner, Computational advantage from quantum-controlled ordering of gates, Phys. Rev. Lett. 113, 250402 (2014), arXiv:1401.8127 [quant-ph].DOI
  19. [19]A. A. Abbott, M. Mhalla, and P. Pocreau, Quantum query complexity of boolean functions under indefinite causal order, Phys. Rev. Res. 6, L032020 (2024), arXiv:2307.10285 [quant-ph].
  20. [20]J. B. Bavaresco, H. Kristjánsson, M. Murao, T. Odake, M. T. Quintino, P. Taranto, and S. Yoshida, Simulating the quantum switch with quantum circuits is computationally hard, Nat. Commun. 16, 10216 (2025), arXiv:2409.18202 [quant-ph].
  21. [21]T. Colnaghi, G. M. D’Ariano, P. Perinotti, and S. Facchini, Quantum computation with programmable connections between gates, Phys. Lett. A 376, 2940 (2012), arXiv:1109.5987 [quant-ph].
  22. [22]S. Facchini and S. Perdrix, Quantum circuits for the unitary permutation problem, in International Conference on Theory and Applications of Models of Computation (Springer, 2015) pp. 324–331, arXiv:1405.5205 [quant-ph].
  23. [23]W. Wei and S. Pang, Extensively causally separable processes admit realizations as quantum circuits with classical control of causal order, arXiv:2609.18559 [quant-ph] (2026).
  24. [24]J. Wechs, A. A. Abbott, and C. Branciard, All causally separable quantum processes are quantum circuits with classical control of causal order, arXiv:2609.20774 [quant-ph] (2026).
  25. [25]P. Lipka-Bartosik, H. Wilming, and N. H. Y. Ng, Catalysis in quantum information theory, Rev. Mod. Phys. 96, 025005 (2024), arXiv:2306.00798 [quant-ph].
  26. [26]S. Yoshida, A. Soeda, and M. Murao, Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly, Phys. Rev. Lett. 131, 120602 (2023), arXiv:2209.02907 [quant-ph].
  27. [27]A. Jamiolkowski, Linear transformations which preserve trace and positive semidefiniteness of operators, Rep. Math. Phys. 3, 275 (1972).
  28. [28]M.-D. Choi, Completely positive linear maps on complex matrices, Linear Algebra Appl. 10, 285 (1975).
  29. [29]D. Kretschmann and R. F. Werner, Quantum channels with memory, Phys. Rev. A 72, 062323 (2005), arXiv:quant-ph/0502106 [quant-ph].DOI
  30. [30]G. Gutoski and J. Watrous, Toward a general theory of quantum games, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC ’07 (2007) pp. 565–574, arXiv:quant-ph/0611234.
  31. [31]L. Hardy, Probability theories with dynamic causal structure: A new framework for quantum gravity, arXiv:gr-qc/0509120 (2005).
  32. [32]A. A. Abbott, C. Giarmatzi, F. Costa, and C. Branciard, Multiparticle causal correlations: Polytopes and inequalities, Phys. Rev. A 94, 032131 (2016), arXiv:1608.01528 [quant-ph].
  33. [33]D. Jonathan and M. B. Plenio, Entanglement-assisted local manipulation of pure quantum states, Phys. Rev. Lett. 83, 3566–3569 (1999), arXiv:quant-ph/9905071.
  34. [34]V. E. Beneš, Optimal rearrangeable multistage connecting networks, Bell System Technical Journal 43, 1641 (1964).DOI
  35. [35]R. Ratan, M. K. Shukla, and A. Y. Oruc, Quantum switching networks with classical routing, in 2007 41st Annual Conference on Information Sciences and Systems (2007) pp. 789–793.

Paper details

vlnc:W_ktnu9uy2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents