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

Journal of Quantum Information Science

Alternative Coins for Quantum Random Walk Search Optimized for a Hypercube

Hristo Tonchev

Published Jan 1, 2015• 5 citations
Publisher

Abstract

The present paper is focused on non-uniform quantum coins for the quantum random walk search algorithm. This is an alternative to the modification of the shift operator, which divides the search space into two parts. This method changes the quantum coins, while the shift operator remains unchanged and sustains the hypercube topology. The results discussed in this paper are obtained by both theoretical calculations and numerical simulations.

DOI
10.4236/jqis.2015.51002

Related papers

Robustness of Quantum Random Walk Search Algorithm in Hypercube when only first or both first and second neighbors are measured

Hristo Tonchev, Petar Danev

In this work we study the robustness of two modifications of quantum random walk search algorithm on hypercube. In the first previously suggested modification, on each even iteration only quantum walk is applied. And in the second, the closest neighbors of the solution are measured classically. In our approach the traversing coin is constructed by both generalized Householder reflection and an additional phase multiplier and we investigate the stability of the algorithm to deviations in those phases. We have shown that the unmodified algorithm becomes more robust when a certain relation between those phases is preserved. The first modification we study here does not lead to any change in the robustness of quantum random walk search algorithm. However, when a measurement of the first and second neighbors is included, there are some differences. The most important one, in view of our study of the robustness, is an increase in the stability of the algorithm, especially for large coin dimensions.

arXiv:2305.15073•May 24, 2023•2 citations

Quantum Random Walks without a Coin Toss

Apoorva D. Patel, K. S. Raghunathan, Pranaw Rungta

We construct a quantum random walk algorithm, based on the Dirac operator instead of the Laplacian. The algorithm explores multiple evolutionary branches by superposition of states, and does not require the coin toss instruction of classical randomised algorithms. We use this algorithm to search for a marked vertex on a hypercubic lattice in arbitrary dimensions. Our numerical and analytical results match the scaling behaviour of earlier algorithms that use a coin toss instruction.

arXiv:quant-ph/0506221•Jun 27, 2005•1 citation

Optimizing the walk coin in the quantum random walk search algorithm

Hristo Tonchev, Petar Danev

This paper examines quantum random walk search algorithm with walk coin constructed by generalized Householder reflection and additional phase shift factor. The results from numerical simulations with neural network show that, with such a construction of the walk coin, the algorithm is more robust to inaccuracies in the specific values of its parameters, as long as it is possible to control the phase difference between the phase shift factor and the phase involved in the Householder reflection. This paper explicitly shows how achieving a properly designed phase difference would make quantum random walk search on a hypercube more robust for coin register consisting of one, two and three qubits.

International Journal of Quantum Information•Jun 19, 2023•2 citations

The uniform measure for quantum walk on hypercube: A quantum Bernoulli noises approach

Ce Wang

In this paper, we present a quantum Bernoulli noises approach to quantum walks on hypercubes. We first obtain an alternative description of a general hypercube, and then, based on the alternative description, we find that the operators ∂k*+∂k behave actually as the shift operators, where ∂k and ∂k* are the annihilation and creation operators acting on Bernoulli functionals, respectively. With the above-mentioned operators as the shift operators on the position space, we introduce a discrete-time quantum walk model on a general hypercube and obtain an explicit formula for calculating its probability distribution at any time. We also establish two limit theorems showing that the averaged probability distribution of the walk even converges to the uniform probability distribution. Finally, we show that the walk produces the uniform measure as its stationary measure on the hypercube provided its initial state satisfies some mild conditions. Some other results are also proven.

arXiv:2211.07948•Journal of Mathematical Physics•Nov 1, 2022•10 citations

Studying the robustness of quantum random walk search on Hypercube against phase errors in the traversing coin by semi-empirical methods

Hristo Tonchev, Petar Danev

In this work we obtain semi-empirical expressions for the probability to find solution of Quantum random walk search algorithm on hypercube when the traversing coin is constructed by generalized Householder reflection and an additional phase shift. Calculations are made for specific relations between coin phases (first from the reflection and second from the shift), that are obtained in our previous works. The quantum algorithm could be made more robust against phase errors, if an experimental implementation preserves those relations. The results from numerical simulations of quantum random walk search algorithm on hypercube are used to find an empirical formulas for algorithm’s probability to find solution. Those formulas, obtained by fitting data to a suitable function, are used to make prognosis about the algorithm’s robustness when dimension of the coin is too large to be simulated on classical computer. Here, we explicitly show all steps of the method used in the paper, while also discuss its advantages and limitations. The goal of this work is to help the experimental implementation of the quantum random walk search algorithm by giving evaluation of the algorithm’s robustness and the obtained probability to find a solution when our design of the walking coin is used.

International Conference of the Balkan Physical Union (BPU)•Oct 2, 2023•1 citation

Quantum walk search for exceptional configurations

Pulak Ranjan Giri

There exist two types of configurations of marked vertices on a two-dimensional grid, known as the exceptional configurations, which are hard to find by the discrete-time quantum walk algorithms. In this article, we provide a comparative study of the quantum walk algorithm with different coins to search these exceptional configurations on a two-dimensional grid. We further extend the analysis to the hypercube, where only one type of exceptional configurations are present. Our observation, backed by numerical results, is that our recently proposed modified coin operator is the only coin which can search both types of exceptional configurations as well as nonexceptional configurations successfully. As a consequence, we observe that the existence of exceptional configurations are not a quantum phenomenon, rather a mere limitation of some of the coin operators.

arXiv:2507.02457•International Journal of Quantum Information•May 17, 2024•2 citations
The present paper is focused on non-uniform quantum coins for the quantum random walk search algorithm. This is an alternative to the modification of the shift operator, which divides the search space into two parts. This method changes the quantum coins, while the shift operator remains unchanged and sustains the hypercube topology. The results discussed in this paper are obtained by both theoretical calculations and numerical simulations.
In this work we study the robustness of two modifications of quantum random walk search algorithm on hypercube. In the first previously suggested modification, on each even iteration only quantum walk is applied. And in the second, the closest neighbors of the solution are measured classically. In our approach the traversing coin is constructed by both generalized Householder reflection and an additional phase multiplier and we investigate the stability of the algorithm to deviations in those phases. We have shown that the unmodified algorithm becomes more robust when a certain relation between those phases is preserved. The first modification we study here does not lead to any change in the robustness of quantum random walk search algorithm. However, when a measurement of the first and second neighbors is included, there are some differences. The most important one, in view of our study of the robustness, is an increase in the stability of the algorithm, especially for large coin dimensions.
This paper examines quantum random walk search algorithm with walk coin constructed by generalized Householder reflection and additional phase shift factor. The results from numerical simulations with neural network show that, with such a construction of the walk coin, the algorithm is more robust to inaccuracies in the specific values of its parameters, as long as it is possible to control the phase difference between the phase shift factor and the phase involved in the Householder reflection. This paper explicitly shows how achieving a properly designed phase difference would make quantum random walk search on a hypercube more robust for coin register consisting of one, two and three qubits.
In this paper, we present a quantum Bernoulli noises approach to quantum walks on hypercubes. We first obtain an alternative description of a general hypercube, and then, based on the alternative description, we find that the operators ∂k*+∂k behave actually as the shift operators, where ∂k and ∂k* are the annihilation and creation operators acting on Bernoulli functionals, respectively. With the above-mentioned operators as the shift operators on the position space, we introduce a discrete-time quantum walk model on a general hypercube and obtain an explicit formula for calculating its probability distribution at any time. We also establish two limit theorems showing that the averaged probability distribution of the walk even converges to the uniform probability distribution. Finally, we show that the walk produces the uniform measure as its stationary measure on the hypercube provided its initial state satisfies some mild conditions. Some other results are also proven.
In this work we obtain semi-empirical expressions for the probability to find solution of Quantum random walk search algorithm on hypercube when the traversing coin is constructed by generalized Householder reflection and an additional phase shift. Calculations are made for specific relations between coin phases (first from the reflection and second from the shift), that are obtained in our previous works. The quantum algorithm could be made more robust against phase errors, if an experimental implementation preserves those relations. The results from numerical simulations of quantum random walk search algorithm on hypercube are used to find an empirical formulas for algorithm’s probability to find solution. Those formulas, obtained by fitting data to a suitable function, are used to make prognosis about the algorithm’s robustness when dimension of the coin is too large to be simulated on classical computer. Here, we explicitly show all steps of the method used in the paper, while also discuss its advantages and limitations. The goal of this work is to help the experimental implementation of the quantum random walk search algorithm by giving evaluation of the algorithm’s robustness and the obtained probability to find a solution when our design of the walking coin is used.
There exist two types of configurations of marked vertices on a two-dimensional grid, known as the exceptional configurations, which are hard to find by the discrete-time quantum walk algorithms. In this article, we provide a comparative study of the quantum walk algorithm with different coins to search these exceptional configurations on a two-dimensional grid. We further extend the analysis to the hypercube, where only one type of exceptional configurations are present. Our observation, backed by numerical results, is that our recently proposed modified coin operator is the only coin which can search both types of exceptional configurations as well as nonexceptional configurations successfully. As a consequence, we observe that the existence of exceptional configurations are not a quantum phenomenon, rather a mere limitation of some of the coin operators.