Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup

Abstract

The usual representation of quantum algorithms, limited to the process of solving the problem, is physically incomplete. We complete it in three steps: (i) extending the representation to the process of setting the problem, (ii) relativizing the extended representation to the problem solver to whom the problem setting must be concealed, and (iii) symmetrizing the relativized representation for time reversal to represent the reversibility of the underlying physical process. The third steps projects the input state of the relativized representation, where the problem solver is completely ignorant of the setting and thus the solution of the problem, on one where she knows half solution (half of the information specifying it when the solution is an unstructured bit string). Completing the physical representation shows that the number of computation steps (oracle queries) required to solve any oracle problem in an optimal quantum way should be that of a classical algorithm endowed with the advanced knowledge of half solution. This fits the major quantum algorithms known today and would solve the quantum query complexity problem.

Explicitly addressed the controversial character of the work in an extended discussion,24 pages

References in corpus (2)

• Disentangling the Quantum World
• Relational Quantum Mechanics

Cited by in corpus (4)

• A relational time-symmetric framework for analyzing the quantum computational speedup
• Back to the seminal Deutsch algorithm
• Forward-backward stochastic simulations: Q-based model for measurement and Bell-nonlocality consistent with weak local realistic premises
• Unobservable causal loops as a way to explain both the quantum computational speedup and quantum nonlocality