The standard model of quantum circuits assumes operations are applied in a fixed sequential “causal” order. In recent years, the possibility of relaxing this constraint to obtain causally indefinite computations has received significant attention. The quantum switch, for example, uses a quantum system to coherently control the order of operations. Several computational and information-theoretical advantages have been demonstrated, raising questions as to whether advantages can be obtained in a more unified complexity theoretic framework. In this paper, we approach this problem by studying the query complexity of Boolean functions under general higher-order quantum computations. To this end, we generalize the framework of query complexity from quantum circuits to quantum supermaps to compare different models on an equal footing. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity, and that any potential advantage arising from causally indefinite supermaps can be bounded by the polynomial method, as is the case with quantum circuits. Nevertheless, we find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps. Published by the American Physical Society 2024
The standard model of quantum circuits assumes operations are applied in a fixed sequential “causal” order. In recent years, the possibility of relaxing this constraint to obtain causally indefinite computations has received significant attention. The quantum switch, for example, uses a quantum system to coherently control the order of operations. Several computational and information-theoretical advantages have been demonstrated, raising questions as to whether advantages can be obtained in a more unified complexity theoretic framework. In this paper, we approach this problem by studying the query complexity of Boolean functions under general higher-order quantum computations. To this end, we generalize the framework of query complexity from quantum circuits to quantum supermaps to compare different models on an equal footing. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity, and that any potential advantage arising from causally indefinite supermaps can be bounded by the polynomial method, as is the case with quantum circuits. Nevertheless, we find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps. Published by the American Physical Society 2024
Computational models typically assume that operations are applied in a fixed sequential order.In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such "causally indefinite" computations can provide advantages in various tasks.Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found.In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -which may exhibit causal indefiniteness -as a generalised computational framework.We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models.Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation.Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.
Quantum theory is consistent with a computational model permitting black-box operations to be applied in an indefinite causal order, going beyond the standard circuit model of computation. The quantum switch -- the simplest such example -- has been shown to provide numerous information-processing advantages. Here, we prove that the action of the quantum switch on two n-qubit quantum channels cannot be simulated deterministically and exactly by any causally ordered quantum circuit that uses M calls to one channel and one call to the other, if M≤max(2,2n−1). This demonstrates an exponential separation in quantum query complexity of indefinite causal order compared to standard quantum circuits.
Quantum supermaps are transformations that map quantum operations to quantum operations.It is known that quantum supermaps which respect a definite, predefined causal order between their input operations correspond to fixed-order quantum circuits, also called quantum combs.A systematic understanding of the physical interpretation of more general types of quantum supermaps-in particular, those incompatible with a definite causal structure-is however lacking.In this paper, we identify two types of circuits that naturally generalize the fixed-order case and that likewise correspond to distinct classes of quantum supermaps, which we fully characterize.We first introduce "quantum circuits with classical control of causal order," in which the order of operations is still well defined, but not necessarily fixed in advance: it can, in particular, be established dynamically, in a classically controlled manner, as the circuit is being used.We then consider "quantum circuits with quantum control of causal order," in which the order of operations is controlled coherently.The supermaps described by these classes of circuits are physically realizable, and the latter encompasses all known examples of physically realizable processes with indefinite causal order, including the celebrated "quantum switch."Interestingly, it also contains other examples arising from the combination of dynamical and coherent control of causal order, and we detail explicitly one such process.Nevertheless, we show that quantum circuits with quantum control of causal order can only generate "causal" correlations, compatible with a well-defined causal order.We furthermore extend our considerations to probabilistic circuits that produce also classical outcomes, and we demonstrate by an example how the characterizations derived in this work allow us to identify advantages for quantum information processing tasks that could be demonstrated in practice.
In recent years, various frameworks have been proposed for the study of quantum processes with indefinite causal order. In particular, quantum circuits with quantum control of causal order (QC-QCs) form a broad class of physical supermaps obtained from a bottom-up construction and are believed to represent all quantum processes physically realisable in a fixed spacetime. Complementarily, the formalism of routed quantum circuits introduces quantum operations constrained by "routes" to represent processes in terms of a more fine-grained routed circuit decomposition. This decomposition, formalised using a so-called routed graph, represents the information flow within the respective process. However, the existence of routed circuit decompositions has only been established for a small set of processes so far, including both certain specific QC-QCs and more exotic processes as examples. In this work, we remedy this fact by connecting these two frameworks. We prove that for any given N, one can use a single routed graph to systematically obtain a routed circuit decomposition for any QC-QC with N parties. We detail this construction explicitly and contrast it with other routed circuit decompositions of QC-QCs, which we obtain from alternative routed graphs. We conclude by pointing out how this connection can be useful to tackle various open problems in the field of indefinite causal order, particularly establishing circuit representations of subclasses of QC-QCs.
Processes with indefinite causal orders (ICOs), such as the quantum switch, are higher-order quantum processes that superpose the order in which quantum operations are performed. Such coherent control yields computational advantages but is not faithfully captured by existing quantum programming languages: either they are restricted to the unitary case, and thus cannot combine ICOs with measurement, or they treat coherent control nonlinearly. In both cases, they do not realize the full computational power of ICOs. We introduce a higher-order quantum functional language that supports general quantum computation, not merely the permutation of channels, and whose linear type system allows quantum control to be well-defined beyond the unitary case, on arbitrary quantum channels. We equip this language with a small-step operational semantics that synchronizes measurement outcomes across superposed branches, using device references and a memory function. We also give a denotational semantics by means of completely positive maps. With linearity as the only constraint, some well-typed terms would denote unphysical maps. We therefore impose a typing discipline that goes beyond linearity, and interpret programs in the causal category Caus[CPM], under which every well-typed program is physically meaningful, a property that can be checked statically and efficiently. We prove soundness, and study the language's expressive power: it can express every quantum channel at first order, and at second order a large subclass of the so-called quantum circuits with quantum control (QC-QCs), containing the quantum switch. Last but not least, we show that this language is well-designed enough to be extended to the nonlinear setting with recursion.
In an ordinary quantum algorithm the gates are applied in a fixed order on the systems. The introduction of indefinite causal structures allows us to relax this constraint and control the order of the gates with an additional quantum state. It is known that this quantum-controlled ordering of gates can reduce the query complexity in deciding a property of black-box unitaries with respect to the best algorithm in which the gates are applied in a fixed order. However, all tasks explicitly found so far require unitaries that either act on unbounded dimensional quantum systems in the asymptotic limit (the limiting case of a large number of black-box gates) or act on qubits, but then involve only a few unitaries. Here we introduce tasks (i) for which there is a provable computational advantage of a quantum-controlled ordering of gates in the asymptotic case and (ii) that require only qubit gates and are therefore suitable to demonstrate this advantage experimentally. We study their solutions with the quantum n-switch and within the quantum circuit model and find that while the n-switch requires to call each gate only once, a causal algorithm has to call at least 2n-1 gates. Furthermore, the best known solution with a fixed gate ordering calls O[n log_{2}(n)] gates.