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

• URL: http://arxiv.org/abs/2506.05187v1
• Date: Thu, 05 Jun 2025 16:00:36 GMT
• Title: Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• Authors: Alastair A. Abbott, Mehdi Mhalla, Pierre Pocreau,
• Abstract summary: Computational models typically assume that operations are applied in a fixed sequential order.<n>Recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure.<n>No separation in exact query complexity has thus-far been found.
• Score: 0.8192907805418583
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
  We show that every computation problem has an exact explicit equation that returns its solution.<n>We present a method to obtain an equation that solves exactly any problem, both inversion, constraint satisfaction and optimization.
  arXiv  Detail & Related papers  (2025-02-09T18:16:53Z)
• The complexity of entanglement embezzlement [0.0]
  We study the circuit complexity of embezzlement using sequences of states that enable arbitrary precision for the process.<n>We imply that circuit complexity acts as a physical obstruction to perfect embezzlement.
  arXiv  Detail & Related papers  (2024-10-24T18:00:33Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  We establish an abstraction of on-the-fly determinization of finite-state automata and demonstrate how it can be applied to bound the automatons. A special case of our findings is that automata with many non-deterministic transitions almost always admit a determinization of complexity.
  arXiv  Detail & Related papers  (2023-08-27T11:51:27Z)
• Real-time Regular Expression Matching [65.268245109828]
  This paper is devoted to finite state automata, regular expression matching, pattern recognition, and the exponential blow-up problem. This paper presents a theoretical and hardware solution to the exponential blow-up problem for some complicated classes of regular languages.
  arXiv  Detail & Related papers  (2023-08-20T09:25:40Z)
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
  We study the query complexity of Boolean functions under general higher order quantum computations. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity. 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  Detail & Related papers  (2023-07-18T13:12:55Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Adaptive n-ary Activation Functions for Probabilistic Boolean Logic [2.294014185517203]
  We show that we can learn arbitrary logic in a single layer using an activation function of matching or greater arity. We represent belief tables using a basis that directly associates the number of nonzero parameters to the effective arity of the belief function. This opens optimization approaches to reduce logical complexity by inducing parameter sparsity.
  arXiv  Detail & Related papers  (2022-03-16T22:47:53Z)
• Bounds on quantum evolution complexity via lattice cryptography [0.0]
  We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators. Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries.
  arXiv  Detail & Related papers  (2022-02-28T16:20:10Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.