Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
arXiv:2307.10285 · doi:10.1103/PhysRevResearch.6.L032020
Abstract
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 ad hoc 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 generalise 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.
arXiv comment7+12 pages
References in corpus (28)
- Advances in Quantum Metrology
- Strengths and Weaknesses of Quantum Computing
- Quantum correlations with no causal order
- Quantum computations without definite causal structure
- Theoretical framework for quantum networks
- Quantum Circuits Architecture
- Transforming quantum operations: quantum supermaps
- Computational advantage from quantum-controlled ordering of gates
- Perfect discrimination of no-signalling channels via quantum superposition of causal structures
- Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
- Witnessing causal nonseparability
- Quantum Metrology with Indefinite Causal Order
- Causal and causally separable processes
- Quantum query complexity of some graph problems
- Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations
- Computational advantage from quantum superposition of multiple temporal orders of photonic gates
- A purification postulate for quantum mechanics with indefinite causal order
- Quantum circuits with classical versus quantum control of causal order
- Experimentally feasible computational advantage from quantum superposition of gate orders
- Optimal Strategies of Quantum Metrology with a Strict Hierarchy
- Quantum computation with indefinite causal structures
- On the definition and characterisation of multipartite causal (non)separability
- Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies
- On exact quantum query complexity
- Deterministic transformations between unitary operations: Exponential advantage with adaptive quantum circuits and the power of indefinite causality
- Reassessing the advantage of indefinite causal orders for quantum metrology
- Existence of processes violating causal inequalities on time-delocalised subsystems
- Composition rules for quantum processes: a no-go theorem