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

Finding Paths via Quantum Systems and its Application for Quantum Algorithms

Daniel Koch

Published Jan 1, 2018• 0 citations
OpenAlex

Abstract

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().

Related papers

Hybrid Quantum Search Algorithms

Vahideh Eshaghian

This thesis presents two main projects focused on hybrid quantum search algorithms. The first, Particle-Guided Grover's Search, applies Bayesian inference to quantum search when the number of solutions is a priori unknown. It begins with a prior distribution that encodes our initial "beliefs" about the true number of solutions in the search space, and recursively updates these beliefs using Bayesian inference. Measurement outcomes of the quantum search that do not yield a solution are interpreted as "evidence", guiding the Bayesian update to determine the optimal number of Grover iterations for subsequent rounds. This approach leverages Particle Filtering -- a Bayesian filtering technique -- to avoid explicitly storing the entire prior distribution at each step. Instead of requiring O(N) memory, the method draws a set of "particles" from the prior and updates their associated weights as quantum search failures accumulate. Particle filtering also offers the advantage of incorporating information from all past failures, rather than only the most recent one. The algorithm's performance is benchmarked against a prior work. The second project, Runtime--Coherence Trade-offs for Hybrid SAT Solvers, is focused on a class of hybrid k-SAT solvers. These solvers are based on a well-known random walk technique called Schoening's algorithm, which uses two sources of randomness to perform a local search over the space of all assignments for a k-SAT problem. In this project, we assume that these sources of randomness are encoded into a long bitstring, allowing the random walk to be interpreted as a deterministic function mapping each bitstring to either 0 or 1, depending on whether the walk successfully finds a satisfying assignment. This functional perspective enables us to pose the question: Given a bound on the coherence time of a quantum computer, which portion of the bitstring should we search coherently, and which portion should be left to classical search? We address this question by introducing a family of hybrid algorithms called "partial Groverizations", which strategically combine quantum and classical resources. We analyze the runtime performance of this family as a function of the available quantum coherence time. The results of this work have been published in IEEE Transactions on Quantum Engineering.

•Jan 1, 2025•0 citations

Discrete quantum walks and quantum image processing

Salvador Elías Venegas-Andraca

In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.

•Jan 1, 2005•19 citations

Discrete quantum walks and quantum image processing

Sougato Bose

In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.

•Jan 1, 2005•0 citations

Finding paths in tree graphs with a quantum walk

Daniel Koch, Mark S. Hillery

We analyze the potential for different types of searches using the formalism of scattering random walks on quantum computers. Given a particular type of graph consisting of nodes and connections, a ``tree maze,'' we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both through numerical calculations as well as by using the eigenvectors and eigenvalues of the quantum system.

arXiv:1710.05084•Physical Review A•Jan 12, 2018•25 citations

The Study of Entangled States in Quantum Computation and Quantum Information Science

Hyeyoun Chung

This thesis explores the use of entangled states in quantum computation and quantum information science. Entanglement, a quantum phenomenon with no classical counterpart, has been identified as an important and quantifiable resource in many areas of theoretical quantum information science, including quantum error correction, quantum cryptography, and quantum algorithms. We first investigate the equivalence classes of a particular class of entangled states (known as graph states due to their association with mathematical graphs) under local operations. We prove that for graph states corresponding to graphs with neither cycles of length 3 nor 4, the equivalence classes can be characterized in a very simple way. We also present software for analyzing and manipulating graph states. We then study quantum error-correcting codes whose codewords are highly entangled states. An important area of investigation concerning QECCs is to determine which resources are necessary in order to carry out any computation on the code to an arbitrary degree of accuracy, while simultaneously maintaining a high degree of resistance to noise. We prove that transversal gates, which are designed to prevent the propagation of errors through a system, are insufficient to achieve universal computation on almost all QECCs. Finally, we study the problem of creating efficient quantum circuits for creating entangling measurements. Entangling measurements can be used to harness the apparent extra computing power of quantum systems by allowing us to extract information about the global, collective properties of a quantum state using local measurements. We construct explicit quantum circuits that create entangling measurements, and show that these circuits scale polynomially in the input parameters.

arXiv:0808.1546•Aug 11, 2008•1 citation

Scattering quantum random walks on square grids and randomly generated mazes

Daniel Koch

The scattering-quantum-random-walk scheme has found success as a basis for search algorithms on highly symmetric graph structures. In this paper we examine its effectiveness at locating a specially marked vertex on square grid graphs, consisting of ${N}^{2}$ nodes. We simulate these quantum systems using classical computational methods and find that the probability distributions that arise are very favorable for a hybrid quantum-classical algorithm. We then examine how this hybrid algorithm handles varying types of randomness in both location of the special vertex and later random obstacles placed throughout the geometry, showing that the algorithm is resilient to both cases.

arXiv:1810.06295•Physical Review A•Jan 18, 2019•4 citations
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().
This thesis presents two main projects focused on hybrid quantum search algorithms. The first, Particle-Guided Grover's Search, applies Bayesian inference to quantum search when the number of solutions is a priori unknown. It begins with a prior distribution that encodes our initial "beliefs" about the true number of solutions in the search space, and recursively updates these beliefs using Bayesian inference. Measurement outcomes of the quantum search that do not yield a solution are interpreted as "evidence", guiding the Bayesian update to determine the optimal number of Grover iterations for subsequent rounds. This approach leverages Particle Filtering -- a Bayesian filtering technique -- to avoid explicitly storing the entire prior distribution at each step. Instead of requiring O(N) memory, the method draws a set of "particles" from the prior and updates their associated weights as quantum search failures accumulate. Particle filtering also offers the advantage of incorporating information from all past failures, rather than only the most recent one. The algorithm's performance is benchmarked against a prior work. The second project, Runtime--Coherence Trade-offs for Hybrid SAT Solvers, is focused on a class of hybrid k-SAT solvers. These solvers are based on a well-known random walk technique called Schoening's algorithm, which uses two sources of randomness to perform a local search over the space of all assignments for a k-SAT problem. In this project, we assume that these sources of randomness are encoded into a long bitstring, allowing the random walk to be interpreted as a deterministic function mapping each bitstring to either 0 or 1, depending on whether the walk successfully finds a satisfying assignment. This functional perspective enables us to pose the question: Given a bound on the coherence time of a quantum computer, which portion of the bitstring should we search coherently, and which portion should be left to classical search? We address this question by introducing a family of hybrid algorithms called "partial Groverizations", which strategically combine quantum and classical resources. We analyze the runtime performance of this family as a function of the available quantum coherence time. The results of this work have been published in IEEE Transactions on Quantum Engineering.
In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.
In this thesis we have focused on two topics: Discrete Quantum Walks and Quantum Image Processing. Our work is a contribution within the field of quantum computation from the perspective of a computer scientist. With the purpose of finding new techniques to develop quantum algorithms, there has been an increasing interest in studying Quantum Walks, the quantum counterparts of classical random walks. Our work in quantum walks begins with a critical and comprehensive assessment of those elements of classical random walks and discrete quantum walks on undirected graphs relevant to algorithm development. We propose a model of discrete quantum walks on an infinite line using pairs of quantum coins under different degrees of entanglement, as well as quantum walkers in different initial state configurations, including superpositions of corresponding basis states. We have found that the probability distributions of such quantum walks have particular forms which are different from the probability distributions of classical random walks. Also, our numerical results show that the symmetry properties of quantum walks with entangled coins have a non-trivial relationship with corresponding initial states and evolution operators. In addition, we have studied the properties of the entanglement generated between walkers, in a family of discrete Hadamard quantum walks on an infinite line with one coin and two walkers. We have found that there is indeed a relation between the amount of entanglement available in each step of the quantum walk and the symmetry of the initial coin state. However, as we show with our numerical simulations, such a relation is not straightforward and, in fact, it can be counterintuitive. Quantum Image Processing is a blend of two fields: quantum computation and image processing. Our aim has been to promote cross-fertilisation and to explore how ideas from quantum computation could be used to develop image processing algorithms. Firstly, we propose methods for storing and retrieving images using non-entangled and entangled qubits. Secondly, we study a case in which 4 different values are randomly stored in a single qubit, and show that quantum mechanical properties can, in certain cases, allow better reproduction of original stored values compared with classical methods. Finally, we briefly note that entanglement may be used as a computational resource to perform hardware-based pattern recognition of geometrical shapes that would otherwise require classical hardware and software.
We analyze the potential for different types of searches using the formalism of scattering random walks on quantum computers. Given a particular type of graph consisting of nodes and connections, a ``tree maze,'' we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both through numerical calculations as well as by using the eigenvectors and eigenvalues of the quantum system.
This thesis explores the use of entangled states in quantum computation and quantum information science. Entanglement, a quantum phenomenon with no classical counterpart, has been identified as an important and quantifiable resource in many areas of theoretical quantum information science, including quantum error correction, quantum cryptography, and quantum algorithms. We first investigate the equivalence classes of a particular class of entangled states (known as graph states due to their association with mathematical graphs) under local operations. We prove that for graph states corresponding to graphs with neither cycles of length 3 nor 4, the equivalence classes can be characterized in a very simple way. We also present software for analyzing and manipulating graph states. We then study quantum error-correcting codes whose codewords are highly entangled states. An important area of investigation concerning QECCs is to determine which resources are necessary in order to carry out any computation on the code to an arbitrary degree of accuracy, while simultaneously maintaining a high degree of resistance to noise. We prove that transversal gates, which are designed to prevent the propagation of errors through a system, are insufficient to achieve universal computation on almost all QECCs. Finally, we study the problem of creating efficient quantum circuits for creating entangling measurements. Entangling measurements can be used to harness the apparent extra computing power of quantum systems by allowing us to extract information about the global, collective properties of a quantum state using local measurements. We construct explicit quantum circuits that create entangling measurements, and show that these circuits scale polynomially in the input parameters.
The scattering-quantum-random-walk scheme has found success as a basis for search algorithms on highly symmetric graph structures. In this paper we examine its effectiveness at locating a specially marked vertex on square grid graphs, consisting of N2{N}^{2}N2 nodes. We simulate these quantum systems using classical computational methods and find that the probability distributions that arise are very favorable for a hybrid quantum-classical algorithm. We then examine how this hybrid algorithm handles varying types of randomness in both location of the special vertex and later random obstacles placed throughout the geometry, showing that the algorithm is resilient to both cases.