Causally indefinite classical processes can compute a constructed Boolean function family with D^0.792 queries instead of D, and indefinite causal order gives an exact three-query quantum algorithm where sequential quantum algorithms need four.
A composition theorem for decision tree complexity
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We completely characterise the complexity in the decision tree model of computing composite relations of the form h = g(f^1,...,f^n), where each relation f^i is boolean-valued. Immediate corollaries include a direct sum theorem for decision tree complexity and a tight characterisation of the decision tree complexity of iterated boolean functions.
citation-role summary
background 1
citation-polarity summary
fields
quant-ph 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
Causally indefinite classical processes can compute a constructed Boolean function family with D^0.792 queries instead of D, and indefinite causal order gives an exact three-query quantum algorithm where sequential quantum algorithms need four.