Reassessing the computational advantage of quantum-controlled ordering of gates

Martin J. Renner, Caslav Brukner

Research on indefinite causal structures is a rapidly evolving field that has a potential not only to make a radical revision of the classical understanding of space-time but also to achieve enhanced functionalities of quantum information processing. For example, it is known that indefinite causal structures provide exponential advantage in communication complexity when compared to causal protocols. In quantum computation, such structures can decide whether two unitary gates commute or anticommute with a single call to each gate, which is impossible with conventional (causal) quantum algorithms. A generalization of this effect to n unitary gates, originally introduced in Araujo et al. [Phys. Lett. 113, 250402 (2014)] and often called Fourier promise problem (FPP), can be solved with the quantum-n-switch and a single call to each gate, while the best known causal algorithm so far calls O(n(2)) gates. In this article, we show that this advantage is smaller than expected. In fact, we present a causal algorithm that solves the only known specific FPP with O(n log (n)) queries and a causal algorithm that solves every FPP with O(n/root n) queries. Besides the interest in such algorithms on their own, our results limit the expected advantage of indefinite causal structures for these problems.

Quantum Optics, Quantum Nanophysics and Quantum Information
External organisation(s)
Vienna Center for Quantum Science and Technology (VCQ), Österreichische Akademie der Wissenschaften (ÖAW)
Physical Review Research
No. of pages
Publication date
Peer reviewed
Austrian Fields of Science 2012
103025 Quantum mechanics
Portal url