2022/05/12 by Jacques Carette, Carette, Jacques, Gerardo Ortiz +4 · 1 voice
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Physical sciences #Programming Languages (cs.PL) #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #cs.PL #quant-ph
paper · pdf · doi:10.48550/arxiv.2205.06346
openalex publication_date 2022/05/12 · arxiv published 2022/05/12 · arxiv updated 2022/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quantum models of computation are widely believed to be more powerful than classical ones. Efforts center on proving that, for a given problem, quantum algorithms are more resource efficient than any classical one. All this, however, assumes a standard predictive paradigm of reasoning where, given initial conditions, the future holds the answer. How about bringing information from the future to the present and exploit it to one's advantage? This is a radical new approach for reasoning, so-called Retrodictive Computation, that benefits from the specific form of the computed functions. We demonstrate how to use tools of symbolic computation to realize retrodictive quantum computing at scale and exploit it to efficiently, and classically, solve instances of the quantum Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, and Shor's algorithms.