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•3 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•10 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.

•May 16, 2018•15 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•252 citations

Decoherence in quantum walks - a review

Kendon, V

The development of quantum walks in the context of quantum computation, as generalisations of random walk techniques, led rapidly to several new quantum algorithms. These all follow 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.

•Jun 1, 2006•211 citations

Discrete Quantum Walks on Graphs and Digraphs

Chris D. Godsil, Hanmeng Zhan

Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.

Cambridge University Press eBooks•Dec 23, 2022•11 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.
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.
The development of quantum walks in the context of quantum computation, as generalisations of random walk techniques, led rapidly to several new quantum algorithms. These all follow 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.
Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.