Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order

Abstract

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.

In Proceedings QPL 2025, arXiv:2508.13619

References in corpus (25)

• 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
• Causal and causally separable processes
• Computational advantage from quantum superposition of multiple temporal orders of photonic gates
• Quantum Computational Complexity in the Presence of Closed Timelike Curves
• Maximal incompatibility of locally classical behavior and global causal order in multi-party scenarios
• Quantum circuits with classical versus quantum control of causal order
• A purification postulate for quantum mechanics with indefinite causal order
• The space of logically consistent classical processes without causal order
• Quantum computation with indefinite causal structures
• Computers with closed timelike curves can solve hard problems
• On the definition and characterisation of multipartite causal (non)separability
• On exact quantum query complexity
• Device-independent test of causal order and relations to fixed-points
• Computational tameness of classical non-causal models
• Unlimited non-causal correlations and their relation to non-locality
• Equivalence of Grandfather and Information Antinomy Under Intervention
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order