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:quant-ph/0610240 · Theoretical Computer Science

Optimal computation with non-unitary quantum walks

Viv M. Kendon, Olivier Maloyer

Published Feb 11, 2008• 20 citations
arXivHTMLPDF
DOI
10.1016/j.tcs.2007.12.011

Related papers

Spectral mapping theorem of an abstract non-unitary quantum walk

Keisuke Asahara, Daiju Funakawa, Etsuo Segawa +2 more

arXiv:2209.13213•Linear Algebra and its Applications•Jul 10, 2023•5 citations

An index theorem for one-dimensional gapless non-unitary quantum walks

Keisuke Asahara, Daiju Funakawa, Motoki Seki +1 more

arXiv:2011.12907•Quantum Information Processing•Sep 1, 2021•7 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

Quantum Walks and Search Algorithms

Renato Portugal

Quantum science and technology•Jan 1, 2013•501 citations

Physical Implementation of Quantum Walks

Kia Manouchehri, Jingbo B. Wang

Springer eBooks•Aug 21, 2013•271 citations

A unified framework for quantum random walk algorithms on general graphs

Yuhan Yang, Tzu-Sheng Chang, Hsu‐Chun Yen

We propose a unified framework for quantum walk algorithms on general graphs, which introduces the concept of unitary labelling into the quantum walk algorithm. In our framework, by assigning the incoming or outgoing arcs of the vertices with distinct labels, unitary properties of the quantum walks can be reserved. For a non-regular graph, auxiliary arcs are added to satisfy the constraint of unitary labelling. For non-unitary quantum walks, under the same framework, we provide a solution by intermediate measurement. This solution performs the Hadamard operator on auxiliary qubits and makes measurement after each step of the walk. Though the unitary constraint can be dissatisfied by applying such a solution, we show that the properties of the quantum walks are still reserved. With this intermediate measurement, the labelling constraint can be alleviated, and the walks on unitary graphs can exhibit the same probability distribution as the unitary quantum walks. Some simulation results over general graphs are given to justify our design.

IEEE Conference on Nanotechnology (IEEE NANO)•Aug 1, 2007•2 citations
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.
We propose a unified framework for quantum walk algorithms on general graphs, which introduces the concept of unitary labelling into the quantum walk algorithm. In our framework, by assigning the incoming or outgoing arcs of the vertices with distinct labels, unitary properties of the quantum walks can be reserved. For a non-regular graph, auxiliary arcs are added to satisfy the constraint of unitary labelling. For non-unitary quantum walks, under the same framework, we provide a solution by intermediate measurement. This solution performs the Hadamard operator on auxiliary qubits and makes measurement after each step of the walk. Though the unitary constraint can be dissatisfied by applying such a solution, we show that the properties of the quantum walks are still reserved. With this intermediate measurement, the labelling constraint can be alleviated, and the walks on unitary graphs can exhibit the same probability distribution as the unitary quantum walks. Some simulation results over general graphs are given to justify our design.