Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup
From MaRDI portal
Publication:1643528
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.
Recommendations
- Quantum algorithms know in advance 50\% of the Solution they will find in the future
- A relational time-symmetric framework for analyzing the quantum computational speedup
- Theory of the quantum speed-up
- The quantum speed up as advanced cognition of the solution
- Highlighting the mechanism of the quantum speedup by time-symmetric and relational quantum mechanics
Cites work
- Can a future choice affect a past measurement's outcome?
- Conservative logic
- Forrelation: a problem that optimally separates quantum from classical computing
- Highlighting the mechanism of the quantum speedup by time-symmetric and relational quantum mechanics
- scientific article; zbMATH DE number 5076264 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 3208040 (Why is no real title available?)
- Irreversibility and Heat Generation in the Computing Process
- On the role of entanglement in quantum-computational speed-up
- Quantum cryptography based on Bell’s theorem
- Quantum search with certainty based on modified Grover algorithms: optimum choice of parameters
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Quantum walks: a comprehensive review
- Rapid solution of problems by quantum computation
- Relational quantum mechanics
- State complexity and quantum computation
- Strengths and Weaknesses of Quantum Computing
- Symmetry of Physical Laws. Part III. Prediction and Retrodiction
- The elusive source of quantum speedup
- Theory of the quantum speed-up
Cited in
(5)- A matrix representation of quantum circuits over non-adjacent qudits
- Quantum algorithms know in advance 50\% of the Solution they will find in the future
- A relational time-symmetric framework for analyzing the quantum computational speedup
- Highlighting the mechanism of the quantum speedup by time-symmetric and relational quantum mechanics
- Theory of the quantum speed-up
This page was built for publication: Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1643528)
