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.
On exact quantum query complexity
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We present several families of total boolean functions which have exact quantum query complexity which is a constant multiple (between 1/2 and 2/3) of their classical query complexity, and show that optimal quantum algorithms for these functions cannot be obtained by simply computing parities of pairs of bits. We also characterise the model of nonadaptive exact quantum query complexity in terms of coding theory and completely characterise the query complexity of symmetric boolean functions in this context. These results were originally inspired by numerically solving the semidefinite programs characterising quantum query complexity for small problem sizes. We include numerical results giving the optimal success probabilities achievable by quantum algorithms computing all boolean functions on up to 4 bits, and all symmetric boolean functions on up to 6 bits.
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.