Computational Advantage from a Quantum Superposition of Qubit Gate Orders

Area of Science:

• Quantum computing
• Quantum information science
• Theoretical computer science

Background:

• Standard quantum algorithms apply gates in a fixed sequence.
• Indefinite causal structures allow quantum-controlled gate ordering using an auxiliary quantum state.
• Previous tasks demonstrating this advantage required either unbounded systems or limited qubit interactions.

Purpose of the Study:

• Introduce new tasks with provable computational advantages for quantum-controlled gate ordering.
• Identify tasks suitable for experimental demonstration using only qubit gates.
• Compare the efficiency of quantum-controlled ordering against fixed-order algorithms and the quantum n-switch.

Main Methods:

• Investigated tasks solvable with quantum-controlled ordering in the asymptotic case.
• Utilized the quantum n-switch framework.
• Analyzed solutions within the standard quantum circuit model.

Main Results:

• Demonstrated provable computational advantage for quantum-controlled ordering in asymptotic qubit-based tasks.
• The quantum n-switch requires only a single call per gate.
• Causal algorithms necessitate at least 2n-1 gate calls, compared to O[n log(n)] for fixed-order algorithms.

Conclusions:

• Quantum-controlled gate ordering provides a significant advantage for specific computational tasks, especially in the asymptotic regime.
• The identified tasks are experimentally feasible using current qubit technologies.
• This work paves the way for practical applications of indefinite causal structures in quantum computation.