Projects per year
Abstract
In an ordinary quantum algorithm the gates are applied in a fixed order on the systems. The introduction of indefinite causal structures allows us to relax this constraint and control the order of the gates with an additional quantum state. It is known that this quantumcontrolled ordering of gates can reduce the query complexity in deciding a property of blackbox unitaries with respect to the best algorithm in which the gates are applied in a fixed order. However, all tasks explicitly found so far require unitaries that either act on unbounded dimensional quantum systems in the asymptotic limit (the limiting case of a large number of blackbox gates) or act on qubits, but then involve only a few unitaries. Here we introduce tasks (i) for which there is a provable computational advantage of a quantumcontrolled ordering of gates in the asymptotic case and (ii) that require only qubit gates and are therefore suitable to demonstrate this advantage experimentally. We study their solutions with the quantum nswitch and within the quantum circuit model and find that while the nswitch requires to call each gate only once, a causal algorithm has to call at least 2n−1 gates. Furthermore, the best known solution with a fixed gate ordering calls O[n log2(n)] gates.
Original language  English 

Article number  230503 
Number of pages  6 
Journal  Physical Review Letters 
Volume  128 
Issue number  23 
DOIs  
Publication status  Published  10 Jun 2022 
Austrian Fields of Science 2012
 103025 Quantum mechanics
 103028 Theory of relativity

Beyond C: Quantum Information Systems Beyond Classical Capabilities
Walther, P., Brukner, C., Briegel, H., Kirchmair, G., Kraus, B., Lechner, W., Monz, T., Weihs, G., Roos, C., Cirac, J. I., Fink, J., Paulovics, V., Dakic, B. & Schuch, N.
1/03/19 → 28/02/27
Project: Research funding
