Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2205.06346

Retrodictive Quantum Computing

Gerardo Ortíz, Jacques Carette, Amr Sabry

Published May 10, 2022• 2 citations
arXivHTMLPDF

Abstract

Abstract Quantum evolution is time-reversible and yet little advantage is gained from this in the circuit model of quantum computing. Indeed, most quantum algorithms expressed in the circuit model compute strictly from the present to the future, preparing initial states and proceeding forward with unitary transformations and measurements. We may call this predictive computation. In contrast, retrodictive quantum theory, retrocausality, and the time-symmetry of physical laws all suggest that quantum computation embodies richer --untapped-- modes of computation, which could exploit knowledge about the future for a computational advantage. We demonstrate that by using symbolic partial evaluation, retrodictive reasoning can indeed be used as a computational resource that exhibits richer modes of computation at the boundary of the classical/quantum divide. Specifically, instead of fully specifying the initial conditions of a quantum circuit and computing forward, it is possible to compute, classically, in both the forward and backward directions starting from partially-specified initial and final conditions. Furthermore, this mixed mode of computation (i) can solve problems with fewer resources than the conventional forward mode of execution, sometimes even purely classically (de-quantization), (ii) can be expressed in a symbolic representation that immediately exposes global relational properties of the wavefunction that are needed for quantum algorithms and (iii) reveals that the entanglement patterns inherent in genuine quantum algorithms with no known classical counterparts are artifacts of the chosen symbolic representation.

DOI
10.21203/rs.3.rs-1626827/v1

Related papers

Symbolic Execution of Hadamard-Toffoli Quantum Circuits

Jacques Carette, Gerardo Ortíz, Amr Sabry

The simulation of quantum programs by classical computers is a critical endeavor for several reasons: it provides proof-of-concept validation of quantum algorithms; it provides opportunities to experiment with new programming abstractions suitable for the quantum domain; and most significantly it is a way to explore the elusive boundary at which a quantum advantage may materialize. Here, we show that traditional techniques of symbolic evaluation and partial evaluation yield surprisingly efficient classical simulations for some instances of textbook quantum algorithms that include the Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, and Shor's algorithms. The success of traditional partial evaluation techniques in this domain is due to one simple insight: the quantum bits used in these algorithms can be modeled by a symbolic boolean variable while still keeping track of the correlations due to superposition and entanglement. More precisely, the system of constraints generated over the symbolic variables contains all the necessary quantum correlations and hence the answer to the quantum algorithms. With a few programming tricks explained in the paper, quantum circuits with millions of gates can be symbolically executed in seconds. Paradoxically, other circuits with as few as a dozen gates take exponential time. We reflect on the significance of these results in the conclusion.

ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM)•Jan 12, 2023•6 citations

Quantum abstract machines without circuits: the need for higher algorithmic expressiveness

Santiago Núñez-Corrales

Existing abstract models of quantum computation make reference to circuit elements, much in contrast to their classical counterparts. Circuits, as a model of computation, substantially limit algorithmic expression and obscure high-level connections between problems and quantum resources. It is argued here that new models are needed to achieve high-level algorithmic expressiveness that allow composable procedural abstractions to manifest, leading to the development of instructions in the sense usually understood in high-level programming languages. Doing so appears essential to the discovery of new quantum algorithms, and deeper understanding of how quantum resources compose into useful patterns, or \emph{quantum motifs}. To achieve this, stronger investment in the intersection between higher-algebra, mathematical physics and quantum science is required to cope with future challenges brought forth by \textit{very large quantum scale integration}.

arXiv:2307.08422•Jul 17, 2023•3 citations

Finding Paths via Quantum Systems and its Application for Quantum Algorithms

Daniel Koch

The field of Quantum Information Theory provides the theoretical foundation for the pursuit of quantum computers. The ongoing questions of how quantum computers will be realized and what they will achieve, are both very uncertain. However, worldwide efforts are beginning to converge on some answers, and the future of quantum computers is looking brighter than ever. In contribution to the grand goal that is quantum computing, this thesis serves as a demonstration to the usefulness of quantum over classical computing. The central theme of my work, and my collaborators, is the exploration of using quantum systems as a tool for path finding and search algorithms. First, we explore a specific problem of sequential measurements in Quantum Information Theory, namely quantum retrodiction. In experiments involving quantum systems with numerous intermediate interactions, often times the only thing that matters to the experimenters is the final measurement. However, quantum retrodiction is the problem of extrapolating information about the past of a quantum system, by studying the present state. The case studied in this dissertation is the retrodiction of a series of two-outcome measurements, the double and triple qubit-interferometers. In both cases, we are presented with the problem of inferring the results of the two-outcome measurements, using only the final state of the system. Specifically, all of the possible outcomes from the measurements result in a different final state, and we are tasked with distinguishing which final state we have. One version of this problem can be seen as light traversing a series of half-silver mirrors, and we would like to know the path the light took. To distinguish which final state we are given, we employ the use of POVMs (Positive-Operator Valued Measurements) that reflect the symmetry of the system. The effectiveness of these POVMs in solving the retrodiction problem are then presented, along with a few comments as to other types of information that can be extracted. Second, we examine a different type of path finding via a quantum system. For a given graph G that can be expressed by connections and nodes, the same graph can be mapped onto a quantum system with a Hilbert space H. All of the connections in the graph can be represented as states in H, and the nodes act as sites for local unitary operations. The sum of all these local operations give rise to U, which is the unitary operator that acts on H, and describes the behavior of the system. Using this formalism, we explore a particular type of U called a scattering quantum random walk. The quantum random walk is the quantum mechanical analogy to the classical random walk, and serves as a powerful tool for searching on a graph. In this dissertation, we present the case of searching for a marked final node, on a graph that consists of a series of stars. The initial state of the system has an equal probability distribution among all states, reflecting no a priori knowledge about the location of the final node. But by applying the quantum random walk, the final state of the system reaches a superposition where nearly all of the probability is concentrated along the path leading to the marked final node. Lastly, we extend this idea of using a quantum random walk to reveal a path even further. We examine a specific type of graph G, called an “N-tree” graph, and apply our quantum random walk scheme. An N-tree graph can be described as a maze where the solver is presented with a junction consisting of N choices. Beyond each choice, is an identical junction of N choices, and so on. The depth of the maze is categorized by a parameter M, thus, to correctly solve the maze one must make M correct choices in succession. Labeling the marked final nodes as F, we present a quantum algorithm that uses a quantum random walk to locate F faster than any classical algorithm. Specifically, the quantum random walk results in a final state of the system with a high probability concentration on all the states leading to F. Two methods for searching for F are then presented. The first approach mimics the ideology of a Grover Search, relying on repetitive searches until F is found. The second approach presents a novel use of past measurements to dictates how the algorithm proceeds next. Specifically, we take advantage of the fact that states along the path leading to F hold most of the probability in the system. In the end, the second quantum algorithm approach provides an speedup over the classical algorithm of the order O().

•Jan 1, 2018•0 citations

Free Quantum Computing

Jacques Carette, Chris Heunen, Robin Kaarsgaard +2 more

Quantum computing improves substantially on known classical algorithms for various important problems, but the nature of the relationship between quantum and classical computing is not yet fully understood. This relationship can be clarified by free models, that add to classical computing just enough physical principles to represent quantum computing and no more. Here we develop an axiomatisation of quantum computing that replaces the standard continuous postulates with a small number of discrete equations, as well as a free model that replaces the standard linear-algebraic model with a category-theoretical one. The axioms and model are based on reversible classical computing, isolate quantum advantage in the ability to take certain well-behaved square roots, and link to various quantum computing hardware platforms. This approach allows combinatorial optimisation, including brute force computer search, to optimise quantum computations. The free model may be interpreted as a programming language for quantum computers, that has the same expressivity and computational universality as the standard model, but additionally allows automated verification and reasoning.

quant-pharXiv:2602.16927•Proceedings of the National Academy of Sciences•Feb 20, 2026•1 citation

Quantum computation for solving linear systems

Yudong Cao

Quantum computation is a subject born out of the combination between physics and computer science. It studies how the laws of quantum mechanics can be exploited to perform computations much more efficiently than current computers (termed classical computers as oppose to quantum computers). The thesis starts by introducing ideas from quantum physics and theoretical computer science and based on these ideas, introducing the basic concepts in quantum computing. These introductory discussions are intended for non-specialists to obtain the essential knowledge needed for understanding the new results presented in the subsequent chapters. After introducing the basics of quantum computing, we focus on the recently proposed quantum algorithm for linear systems. The new results include i) special instances of quantum circuits that can be implemented using current experimental resources; ii) detailed quantum algorithms that are suitable for a broader class of linear systems. We show that for some particular problems the quantum algorithm is able to achieve exponential speedup over their classical counterparts.

•Jan 1, 2013•0 citations

Time Reversal Symmetry and Collapse Models

Daniel Bedingham, O. J. E. Maroney

Dynamical collapse models embody the idea of a physical collapse of the wave function in a mathematically well-defined way. They involve modifications to the standard rules of quantum theory in order to describe collapse as a physical process. This appears to introduce a time reversal asymmetry into the dynamics since the state at any given time depends on collapses in the past but not in the future. Here we challenge this conclusion by demonstrating that, subject to specified model constraints, collapse models can be given a structurally time symmetric formulation in which the collapse events are the primitive objects of the theory. Three different examples of time asymmetries associated with collapse models are then examined and in each case it is shown that the same dynamical rule determining the collapse events works in both the forward and backward in time directions. Any physically observed time asymmetries that arise in such models are due to the asymmetric imposition of initial or final time boundary conditions, rather than from an inherent asymmetry in the dynamical law. This is the standard explanation of time asymmetric behaviour resulting from time symmetric laws.

Foundations of Physics•Apr 8, 2017•8 citations
Abstract Quantum evolution is time-reversible and yet little advantage is gained from this in the circuit model of quantum computing. Indeed, most quantum algorithms expressed in the circuit model compute strictly from the present to the future, preparing initial states and proceeding forward with unitary transformations and measurements. We may call this predictive computation. In contrast, retrodictive quantum theory, retrocausality, and the time-symmetry of physical laws all suggest that quantum computation embodies richer --untapped-- modes of computation, which could exploit knowledge about the future for a computational advantage. We demonstrate that by using symbolic partial evaluation, retrodictive reasoning can indeed be used as a computational resource that exhibits richer modes of computation at the boundary of the classical/quantum divide. Specifically, instead of fully specifying the initial conditions of a quantum circuit and computing forward, it is possible to compute, classically, in both the forward and backward directions starting from partially-specified initial and final conditions. Furthermore, this mixed mode of computation (i) can solve problems with fewer resources than the conventional forward mode of execution, sometimes even purely classically (de-quantization), (ii) can be expressed in a symbolic representation that immediately exposes global relational properties of the wavefunction that are needed for quantum algorithms and (iii) reveals that the entanglement patterns inherent in genuine quantum algorithms with no known classical counterparts are artifacts of the chosen symbolic representation.
The simulation of quantum programs by classical computers is a critical endeavor for several reasons: it provides proof-of-concept validation of quantum algorithms; it provides opportunities to experiment with new programming abstractions suitable for the quantum domain; and most significantly it is a way to explore the elusive boundary at which a quantum advantage may materialize. Here, we show that traditional techniques of symbolic evaluation and partial evaluation yield surprisingly efficient classical simulations for some instances of textbook quantum algorithms that include the Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, and Shor's algorithms. The success of traditional partial evaluation techniques in this domain is due to one simple insight: the quantum bits used in these algorithms can be modeled by a symbolic boolean variable while still keeping track of the correlations due to superposition and entanglement. More precisely, the system of constraints generated over the symbolic variables contains all the necessary quantum correlations and hence the answer to the quantum algorithms. With a few programming tricks explained in the paper, quantum circuits with millions of gates can be symbolically executed in seconds. Paradoxically, other circuits with as few as a dozen gates take exponential time. We reflect on the significance of these results in the conclusion.
Existing abstract models of quantum computation make reference to circuit elements, much in contrast to their classical counterparts. Circuits, as a model of computation, substantially limit algorithmic expression and obscure high-level connections between problems and quantum resources. It is argued here that new models are needed to achieve high-level algorithmic expressiveness that allow composable procedural abstractions to manifest, leading to the development of instructions in the sense usually understood in high-level programming languages. Doing so appears essential to the discovery of new quantum algorithms, and deeper understanding of how quantum resources compose into useful patterns, or \emph{quantum motifs}. To achieve this, stronger investment in the intersection between higher-algebra, mathematical physics and quantum science is required to cope with future challenges brought forth by \textit{very large quantum scale integration}.
The field of Quantum Information Theory provides the theoretical foundation for the pursuit of quantum computers. The ongoing questions of how quantum computers will be realized and what they will achieve, are both very uncertain. However, worldwide efforts are beginning to converge on some answers, and the future of quantum computers is looking brighter than ever. In contribution to the grand goal that is quantum computing, this thesis serves as a demonstration to the usefulness of quantum over classical computing. The central theme of my work, and my collaborators, is the exploration of using quantum systems as a tool for path finding and search algorithms. First, we explore a specific problem of sequential measurements in Quantum Information Theory, namely quantum retrodiction. In experiments involving quantum systems with numerous intermediate interactions, often times the only thing that matters to the experimenters is the final measurement. However, quantum retrodiction is the problem of extrapolating information about the past of a quantum system, by studying the present state. The case studied in this dissertation is the retrodiction of a series of two-outcome measurements, the double and triple qubit-interferometers. In both cases, we are presented with the problem of inferring the results of the two-outcome measurements, using only the final state of the system. Specifically, all of the possible outcomes from the measurements result in a different final state, and we are tasked with distinguishing which final state we have. One version of this problem can be seen as light traversing a series of half-silver mirrors, and we would like to know the path the light took. To distinguish which final state we are given, we employ the use of POVMs (Positive-Operator Valued Measurements) that reflect the symmetry of the system. The effectiveness of these POVMs in solving the retrodiction problem are then presented, along with a few comments as to other types of information that can be extracted. Second, we examine a different type of path finding via a quantum system. For a given graph G that can be expressed by connections and nodes, the same graph can be mapped onto a quantum system with a Hilbert space H. All of the connections in the graph can be represented as states in H, and the nodes act as sites for local unitary operations. The sum of all these local operations give rise to U, which is the unitary operator that acts on H, and describes the behavior of the system. Using this formalism, we explore a particular type of U called a scattering quantum random walk. The quantum random walk is the quantum mechanical analogy to the classical random walk, and serves as a powerful tool for searching on a graph. In this dissertation, we present the case of searching for a marked final node, on a graph that consists of a series of stars. The initial state of the system has an equal probability distribution among all states, reflecting no a priori knowledge about the location of the final node. But by applying the quantum random walk, the final state of the system reaches a superposition where nearly all of the probability is concentrated along the path leading to the marked final node. Lastly, we extend this idea of using a quantum random walk to reveal a path even further. We examine a specific type of graph G, called an “N-tree” graph, and apply our quantum random walk scheme. An N-tree graph can be described as a maze where the solver is presented with a junction consisting of N choices. Beyond each choice, is an identical junction of N choices, and so on. The depth of the maze is categorized by a parameter M, thus, to correctly solve the maze one must make M correct choices in succession. Labeling the marked final nodes as F, we present a quantum algorithm that uses a quantum random walk to locate F faster than any classical algorithm. Specifically, the quantum random walk results in a final state of the system with a high probability concentration on all the states leading to F. Two methods for searching for F are then presented. The first approach mimics the ideology of a Grover Search, relying on repetitive searches until F is found. The second approach presents a novel use of past measurements to dictates how the algorithm proceeds next. Specifically, we take advantage of the fact that states along the path leading to F hold most of the probability in the system. In the end, the second quantum algorithm approach provides an speedup over the classical algorithm of the order O().
Quantum computing improves substantially on known classical algorithms for various important problems, but the nature of the relationship between quantum and classical computing is not yet fully understood. This relationship can be clarified by free models, that add to classical computing just enough physical principles to represent quantum computing and no more. Here we develop an axiomatisation of quantum computing that replaces the standard continuous postulates with a small number of discrete equations, as well as a free model that replaces the standard linear-algebraic model with a category-theoretical one. The axioms and model are based on reversible classical computing, isolate quantum advantage in the ability to take certain well-behaved square roots, and link to various quantum computing hardware platforms. This approach allows combinatorial optimisation, including brute force computer search, to optimise quantum computations. The free model may be interpreted as a programming language for quantum computers, that has the same expressivity and computational universality as the standard model, but additionally allows automated verification and reasoning.
Quantum computation is a subject born out of the combination between physics and computer science. It studies how the laws of quantum mechanics can be exploited to perform computations much more efficiently than current computers (termed classical computers as oppose to quantum computers). The thesis starts by introducing ideas from quantum physics and theoretical computer science and based on these ideas, introducing the basic concepts in quantum computing. These introductory discussions are intended for non-specialists to obtain the essential knowledge needed for understanding the new results presented in the subsequent chapters. After introducing the basics of quantum computing, we focus on the recently proposed quantum algorithm for linear systems. The new results include i) special instances of quantum circuits that can be implemented using current experimental resources; ii) detailed quantum algorithms that are suitable for a broader class of linear systems. We show that for some particular problems the quantum algorithm is able to achieve exponential speedup over their classical counterparts.
Dynamical collapse models embody the idea of a physical collapse of the wave function in a mathematically well-defined way. They involve modifications to the standard rules of quantum theory in order to describe collapse as a physical process. This appears to introduce a time reversal asymmetry into the dynamics since the state at any given time depends on collapses in the past but not in the future. Here we challenge this conclusion by demonstrating that, subject to specified model constraints, collapse models can be given a structurally time symmetric formulation in which the collapse events are the primitive objects of the theory. Three different examples of time asymmetries associated with collapse models are then examined and in each case it is shown that the same dynamical rule determining the collapse events works in both the forward and backward in time directions. Any physically observed time asymmetries that arise in such models are due to the asymmetric imposition of initial or final time boundary conditions, rather than from an inherent asymmetry in the dynamical law. This is the standard explanation of time asymmetric behaviour resulting from time symmetric laws.