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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Quantum walk search factors in the regime of weak measurement

Debabrata Ghoshal

Published Jun 11, 2014• 0 citations
Publisher

Abstract

Our previous work brought some interesting results of the discrete Quantum Walks in the regime of Weak Measurement (QWWM or QWWV). Using the knowledge of such results of QWWM, we are now exploring the search algorithms and investigating the factors associated with such walk. The study of such factors like dimensionality, connectivity of the dataset and the strength of disorder or percolation are already studied by others in the context of general quantum walks. It is our interest to show the similarities and/or differences of such factors of general quantum walks with QWWV. The subject of decoherence in quantum walks is another challenging research topic at present. We are also exploring the topic of decoherence in QWWM or QWWV.

DOI
10.1117/12.2050932

Related papers

A statistical and comparative study of quantum walks under weak measurements and weak values regimes

Debabrata Ghoshal, Marco O. Lanzagorta, Salvador Elías Venegas-Andraca

Quantum walks have been studied under several regimes. Motivated by experimental results on quantum weak measurements and weak values as well as by the need to develop new insights for quantum algorithm development, we are extending our knowledge by studying the behavior of quantum walks under the regime of quantum weak measurements and weak values of pre- and postselected measurements (QWWM hereinafter). In particular, we investigate the limiting position probability distribution and several statistical measures (such as standard deviation) of a QWWM on an infinite line, and compare such results with corresponding classical and quantum walks position probability distributions and statistical measures, stressing the differences provided by weak measurements and weak values with respect to results computed by using canonical observables. We start by producing a concise introduction to quantum weak values and quantum weak measurements. We then introduce definitions as well as both analytical and numerical results for a QWWM under Hadamard evolution and extend our analysis to quantum evolution ruled by general unitary operators. Moreover, we propose a definition and focus on the properties of mixing time of QWWM on an infinite line, followed by a comparison of known corresponding results for classical and quantum walks mixing times. We finish this paper by presenting a plausible experimental implementation of a QWWM.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 13, 2011•2 citations

The quantum walk search algorithm: factors affecting efficiency

Neil B. Lovett, Matthew Everitt, Robert M. Heath +1 more

We carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi et al. (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.

arXiv:1110.4366•Mathematical Structures in Computer Science•May 16, 2018•17 citations

Decoherence in quantum walks – a review

Viv M. Kendon

The development of quantum walks in the context of quantum computation, as generalisations of random walk techniques, has led rapidly to several new quantum algorithms. These all follow a unitary quantum evolution, apart from the final measurement. Since logical qubits in a quantum computer must be protected from decoherence by error correction, there is no need to consider decoherence at the level of algorithms. Nonetheless, enlarging the range of quantum dynamics to include non-unitary evolution provides a wider range of possibilities for tuning the properties of quantum walks. For example, small amounts of decoherence in a quantum walk on the line can produce more uniform spreading (a top-hat distribution), without losing the quantum speed up. This paper reviews the work on decoherence, and more generally on non-unitary evolution, in quantum walks and suggests what future questions might prove interesting to pursue in this area.

arXiv:quant-ph/0606016•Mathematical Structures in Computer Science•Nov 23, 2007•363 citations

Some Statistical Measures and Analytical Results of Quantum Walks under Weak Measurement and Weak Values Regime

Debabrata Ghoshal, Marco O. Lanzagorta, Salvador Elías Venegas-Andraca

Bulletin of the American Physical Society•Mar 22, 2011•0 citations

Application of quantum walks on graph structures to quantum computing

Neil B. Lovett

Quantum computation is a new computational paradigm which can provide fundamentally faster computation than in the classical regime. This is dependent on finding efficient quantum algorithms for problems of practical interest. One of the most successful tools in developing new quantum algorithms is the quantum walk. In this thesis, we explore two applications of the discrete time quantum walk. In addition, we introduce an experimental scheme for generating cluster states, a universal resource for quantum computation. We give an explicit construction which provides a link between the circuit model of quantum computation, and a graph structure on which the discrete time quantum walk traverses, performing the same computation. We implement a universal gate set, proving the discrete time quantum walk is universal for quantum computation, thus confirming any quantum algorithm can be recast as a quantum walk algorithm. In addition, we study factors affecting the efficiency of the quantum walk search algorithm. Although there is a strong dependence on the spatial dimension of the structure being searched, we find secondary dependencies on other factors including the connectivity and disorder (symmetry). Fairly intuitively, as the connectivity increases, the efficiency of the algorithm increases, as the walker can coalesce on the marked state with higher probability in a quicker time. In addition, we find as disorder in the system increases, the algorithm can maintain the quantum speed up for a certain level of disorder before gradually reverting to the classical run time. Finally, we give an abstract scheme for generating cluster states. We see a linear scaling, better than many schemes, as doubling the size of the generating grid in our scheme produces a cluster state which is double the depth. Our scheme is able to create other interesting topologies of entangled states, including the unit cell for topological error correcting schemes.

•Mar 1, 2011•6 citations

Decoherence and Quantum Walks under the regime of weak measurements and weak values

Debabrata Ghoshal, Marco O. Lanzagorta, Salvador Elías Venegas-Andraca

Bulletin of the American Physical Society•Feb 28, 2012•0 citations
Our previous work brought some interesting results of the discrete Quantum Walks in the regime of Weak Measurement (QWWM or QWWV). Using the knowledge of such results of QWWM, we are now exploring the search algorithms and investigating the factors associated with such walk. The study of such factors like dimensionality, connectivity of the dataset and the strength of disorder or percolation are already studied by others in the context of general quantum walks. It is our interest to show the similarities and/or differences of such factors of general quantum walks with QWWV. The subject of decoherence in quantum walks is another challenging research topic at present. We are also exploring the topic of decoherence in QWWM or QWWV.
Quantum walks have been studied under several regimes. Motivated by experimental results on quantum weak measurements and weak values as well as by the need to develop new insights for quantum algorithm development, we are extending our knowledge by studying the behavior of quantum walks under the regime of quantum weak measurements and weak values of pre- and postselected measurements (QWWM hereinafter). In particular, we investigate the limiting position probability distribution and several statistical measures (such as standard deviation) of a QWWM on an infinite line, and compare such results with corresponding classical and quantum walks position probability distributions and statistical measures, stressing the differences provided by weak measurements and weak values with respect to results computed by using canonical observables. We start by producing a concise introduction to quantum weak values and quantum weak measurements. We then introduce definitions as well as both analytical and numerical results for a QWWM under Hadamard evolution and extend our analysis to quantum evolution ruled by general unitary operators. Moreover, we propose a definition and focus on the properties of mixing time of QWWM on an infinite line, followed by a comparison of known corresponding results for classical and quantum walks mixing times. We finish this paper by presenting a plausible experimental implementation of a QWWM.
We carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi et al. (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.
The development of quantum walks in the context of quantum computation, as generalisations of random walk techniques, has led rapidly to several new quantum algorithms. These all follow a unitary quantum evolution, apart from the final measurement. Since logical qubits in a quantum computer must be protected from decoherence by error correction, there is no need to consider decoherence at the level of algorithms. Nonetheless, enlarging the range of quantum dynamics to include non-unitary evolution provides a wider range of possibilities for tuning the properties of quantum walks. For example, small amounts of decoherence in a quantum walk on the line can produce more uniform spreading (a top-hat distribution), without losing the quantum speed up. This paper reviews the work on decoherence, and more generally on non-unitary evolution, in quantum walks and suggests what future questions might prove interesting to pursue in this area.
Quantum computation is a new computational paradigm which can provide fundamentally faster computation than in the classical regime. This is dependent on finding efficient quantum algorithms for problems of practical interest. One of the most successful tools in developing new quantum algorithms is the quantum walk. In this thesis, we explore two applications of the discrete time quantum walk. In addition, we introduce an experimental scheme for generating cluster states, a universal resource for quantum computation. We give an explicit construction which provides a link between the circuit model of quantum computation, and a graph structure on which the discrete time quantum walk traverses, performing the same computation. We implement a universal gate set, proving the discrete time quantum walk is universal for quantum computation, thus confirming any quantum algorithm can be recast as a quantum walk algorithm. In addition, we study factors affecting the efficiency of the quantum walk search algorithm. Although there is a strong dependence on the spatial dimension of the structure being searched, we find secondary dependencies on other factors including the connectivity and disorder (symmetry). Fairly intuitively, as the connectivity increases, the efficiency of the algorithm increases, as the walker can coalesce on the marked state with higher probability in a quicker time. In addition, we find as disorder in the system increases, the algorithm can maintain the quantum speed up for a certain level of disorder before gradually reverting to the classical run time. Finally, we give an abstract scheme for generating cluster states. We see a linear scaling, better than many schemes, as doubling the size of the generating grid in our scheme produces a cluster state which is double the depth. Our scheme is able to create other interesting topologies of entangled states, including the unit cell for topological error correcting schemes.