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:2401.03602 · Results in Physics

Robustness of different modifications of Grover’s algorithm based on generalized Householder reflections with different phases

Hristo Tonchev, Petar Danev

Published Mar 23, 2024• 4 citations
arXivHTMLPDF

Abstract

In this work we study five Grover’s algorithm modifications, where each iteration is constructed by two generalized Householder reflections, against inaccuracies in the phases. By using semi-empirical methods, we investigate various characteristics of the dependence between the probability to find solution and the phase errors. The first of them is the robustness of the probability to errors in the phase. The second one is how quickly the probability falls beyond the stability interval. And finally, the average success rate of the algorithm when the parameters are in the range of the highly robust interval. Two of the modifications require usage of the same Grover operator each iteration and in the other three it differs. Those semi-empirical methods give us the tool to make prediction of the quantum algorithm modifications’ overall behavior and compare them for even larger register size.

DOI
10.1016/j.rinp.2024.107595

Related papers

Semi-empirical method for evaluating the robustness of QRWS algorithm for different coin sizes and functional dependence between coin phases

Hristo Tonchev, Petar Danev

Abstract In this work we study the quantum random walk search algorithm when the walk coin is constructed by generalized Householder reflection and a phase multiplier. We focus on the algorithm’s robustness against errors in the phases – how the probability to find solution decreases with increasing the errors in those phases. The robustness depends on the functional dependence between the reflection phase φ and the phase multiplier ζ. Here we use interpolations by non-linear logistic regression functions to study a particular functional dependence between angles ζ = -2φ + 3π + α sin(2φ) for different coin sizes and parameters alpha. The obtained results in this work are discussed, together with their limitations.

Journal of Physics Conference Series•Feb 1, 2024•0 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

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

Reducing number of gates in quantum random walk search algorithm via modification of coin operators

Hristo Tonchev, Petar Danev

This paper examines a way to simplify the circuit of quantum random walk search algorithm, when the traversing coin is constructed by both generalized Householder reflection and an additional phase multiplier. If an appropriate relation between corresponding parameters is realized, our algorithm becomes more robust to deviations in the phases. In this modification marking coin is not needed, and all advantages from above mentioned optimization to the stability, are preserved. It is shown explicitly how to construct such walk coin in order to obtain more robust quantum algorithm.

arXiv:2204.12858•Results in Physics•Mar 1, 2023•6 citations

A Machine Learning Study of High Robustness Quantum Walk Search Algorithm with Qudit Householder Coins

Hristo Tonchev, Petar Danev

In this work, the quantum random walk search algorithm with a walk coin constructed by generalized Householder reflection and phase multiplier has been studied. The coin register is one qudit with an arbitrary dimension. Monte Carlo simulations, in combination with supervised machine learning, are used to find walk coins that make the quantum algorithm more robust to deviations in the coin’s parameters. This is achieved by introducing functional dependence between these parameters. The functions that give the best performance of the algorithm are studied in detail by numerical statistical methods. A thorough comparison between our modification and an algorithm, with coins made using only Householder reflection, shows significant advantages of the former. By applying a deep neural network, we make a prediction for the parameters of an optimal coin with an arbitrary size and estimate the algorithm’s stability for such a coin.

Algorithms•Mar 9, 2023•2 citations

Phase Matching for a Generalized Grover's Algorithm

Chris Cardullo, Min Kang

We study the fully generalized Grover's algorithm to find the optimal phase changes for each step of the iteration to maximize gain in probability of observation of the target, and when phase matching is required. We find that classical Grover's algorithm and phase matching remains to be optimal till the target probability gets close 1. However, as the probability of observation approaches 1, the optimal phase changes differ from $π$ and no longer observe phase matching. We provide the optimization statement to find the optimal phase changes given the current amplitude vector and the size of the set. To analyze this formula, we approach it from a numerical and analytical perspective, with the analytical perspective focusing on special cases that simplify the optimization and allow for general statements about its behavior. Finally, we provide an example of a 5 qubit system and show that for the final iteration the optimal phase changes differ from traditional Grover's algorithm and do not observe phase matching, but lead to an increase in the probability of the target.

quant-pharXiv:2605.13758•May 14, 2026•0 citations
In this work we study five Grover’s algorithm modifications, where each iteration is constructed by two generalized Householder reflections, against inaccuracies in the phases. By using semi-empirical methods, we investigate various characteristics of the dependence between the probability to find solution and the phase errors. The first of them is the robustness of the probability to errors in the phase. The second one is how quickly the probability falls beyond the stability interval. And finally, the average success rate of the algorithm when the parameters are in the range of the highly robust interval. Two of the modifications require usage of the same Grover operator each iteration and in the other three it differs. Those semi-empirical methods give us the tool to make prediction of the quantum algorithm modifications’ overall behavior and compare them for even larger register size.
Abstract In this work we study the quantum random walk search algorithm when the walk coin is constructed by generalized Householder reflection and a phase multiplier. We focus on the algorithm’s robustness against errors in the phases – how the probability to find solution decreases with increasing the errors in those phases. The robustness depends on the functional dependence between the reflection phase φ and the phase multiplier ζ. Here we use interpolations by non-linear logistic regression functions to study a particular functional dependence between angles ζ = -2φ + 3π + α sin(2φ) for different coin sizes and parameters alpha. The obtained results in this work are discussed, together with their limitations.
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.
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 a way to simplify the circuit of quantum random walk search algorithm, when the traversing coin is constructed by both generalized Householder reflection and an additional phase multiplier. If an appropriate relation between corresponding parameters is realized, our algorithm becomes more robust to deviations in the phases. In this modification marking coin is not needed, and all advantages from above mentioned optimization to the stability, are preserved. It is shown explicitly how to construct such walk coin in order to obtain more robust quantum algorithm.
In this work, the quantum random walk search algorithm with a walk coin constructed by generalized Householder reflection and phase multiplier has been studied. The coin register is one qudit with an arbitrary dimension. Monte Carlo simulations, in combination with supervised machine learning, are used to find walk coins that make the quantum algorithm more robust to deviations in the coin’s parameters. This is achieved by introducing functional dependence between these parameters. The functions that give the best performance of the algorithm are studied in detail by numerical statistical methods. A thorough comparison between our modification and an algorithm, with coins made using only Householder reflection, shows significant advantages of the former. By applying a deep neural network, we make a prediction for the parameters of an optimal coin with an arbitrary size and estimate the algorithm’s stability for such a coin.
We study the fully generalized Grover's algorithm to find the optimal phase changes for each step of the iteration to maximize gain in probability of observation of the target, and when phase matching is required. We find that classical Grover's algorithm and phase matching remains to be optimal till the target probability gets close 1. However, as the probability of observation approaches 1, the optimal phase changes differ from πππ and no longer observe phase matching. We provide the optimization statement to find the optimal phase changes given the current amplitude vector and the size of the set. To analyze this formula, we approach it from a numerical and analytical perspective, with the analytical perspective focusing on special cases that simplify the optimization and allow for general statements about its behavior. Finally, we provide an example of a 5 qubit system and show that for the final iteration the optimal phase changes differ from traditional Grover's algorithm and do not observe phase matching, but lead to an increase in the probability of the target.