Foundations of Physics 48 (3):333-354 (2018)

The usual representation of quantum algorithms, limited to the process of solving the problem, is physically incomplete. We complete it in three steps: extending the representation to the process of setting the problem, relativizing the extended representation to the problem solver to whom the problem setting must be concealed, and 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 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. Completing the physical representation shows that the number of computation steps 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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/s10701-018-0146-3
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 62,268
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Algorithms for Quantum Computation: Discrete Logarithms and Factoring.P. Shor - 1994 - Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science:124-134.
On the Role of Entanglement in Quantum-Computational Speed-Up.Richard Jozsa & Noah Linden - 2003 - Proceedings of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences 459:2011--2032.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

On the Physical Explanation for Quantum Computational Speedup.Michael Cuffaro - 2013 - Dissertation, The University of Western Ontario
How to Interpret Quantum Mechanics.Jeffrey Bub - 1994 - Erkenntnis 41 (2):253 - 273.
Problem Solving and Situated Cognition.David Kirsh - 2009 - In Philip Robbins & M. Aydede (eds.), The Cambridge Handbook of Situated Cognition. Cambridge: Cambridge University Press. pp. 264--306.
Problem Solving and Situated Cognition.David Kirsh - 2009 - The Cambridge Handbook of Situated Cognition:264-306.
Quantum Hypercomputability?Amit Hagar & Alexandre Korolev - 2006 - Minds and Machines 16 (1):87-93.
Problem Representation for Refinement.Halil A. Guvenir & Varol Akman - 1992 - Minds and Machines 2 (3):267-282.
Models as Make-Believe.Adam Toon - 2010 - In Roman Frigg & Matthew Hunter (eds.), Beyond Mimesis and Convention: Representation in Art and Science. Boston Studies in Philosophy of Science.
Realism and Representation: The Case of Rembrandt's Hat.Michael Morris - 2015 - European Journal of Philosophy 23 (4):909-932.
The Representation of Time and Change in Mechanics.Gordon Belot - 2005 - In John Earman & Jeremy Butterfield (eds.), Philosophy of Physics. Elsevier. pp. 133--227.


Added to PP index

Total views
15 ( #671,644 of 62,229 )

Recent downloads (6 months)
1 ( #457,173 of 62,229 )

How can I increase my downloads?


My notes