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

Lobachevskii Journal of Mathematics

Quantum Amplitude Amplification Algorithm Simulation for Prediction of a Binary Classification Problem

Liliya Safina

Published Feb 1, 2023• 2 citations
Publisher

Abstract

Abstract In this work, we present our experiment’s results where we simulate the quantum amplitude amplification algorithm for a prediction problem. The problem is to calculate the total probability of a good class by an ensemble model. Theoretically, the quantum prediction will be quadratically faster than a classical prediction. We need to get outputs (probabilities of the good class) of all classifiers. After that, by summation the probabilities the ensemble model returns the total probability of the good class for an input object. Let us demonstrate how the quantum amplitude amplification algorithm allows us to estimate the total probability. In this experiment, we count an iterations number of quantum search running to estimate the total probability.

DOI
10.1134/s1995080223020324

Related papers

The quantum version of prediction for binary classification problem by ensemble methods

Kamil Ravilevich Khadiev, Liliya Safina

In this work, we consider the performance of using a quantum algorithm to predict the result of a binary classification problem when a machine learning model is an ensemble of any simple classifiers. This approach is faster than classical prediction and uses quantum and classical computing, but it is based on a probabilistic algorithm. Let N be the number of classifiers from an ensemble model and O(T) be the running time of prediction of one classifier. In classical case, the final result is obtained by ”averaging” outcomes of all ensemble model’s classifiers. The running time in classical case is O (N · T). We propose an algorithm that works in O (√N · T ).

arXiv:2112.13346•International Conference on Micro- and Nano-Electronics (ICMNE)•Jan 31, 2022•10 citations

Quantum simulator experiment for binary classification prognostication via ensemble methods

Kamil Ravilevich Khadiev, Liliya Safina

In this work, we conducted an experiment on a quantum simulator for tasks of binary classification by the random forest method, estimated the time the complexity of the classical and quantum versions of the algorithms, as well as memory complexity of the algorithm for the quantum version. Previously we received temporal acceleration of the algorithm for prediction by using quantum amplitude amplification algorithm, and now tested the algorithm proposed by us on our quantum simulator and analyzed the predictive results.

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"•Jan 1, 2022•0 citations

Chapter 4: Amplitude amplification and estimation

Giacomo Nannicini

In Chs. 2 and 3 we described several quantum algorithms that are exponentially faster than classical algorithms for the same problem, under some measure of complexity. Unfortunately, the algorithms of Ch. 2 apply to rather contrived problems that do not have known direct applications. We now describe a quantum algorithm that gives only a polynomial—more specifically, quadratic—speedup with respect to classical algorithms, but it applies to a large class of problems and finds many useful applications, both directly and as an algorithmic design tool. The algorithm is known as Grover’s search [89], and its generalization is known as amplitude amplification [43]. Amplitude amplification is widely used as part of many quantum algorithms. It also serves as the basis for amplitude estimation, a way of estimating probabilities quadratically faster than with classical Monte Carlo, and for quantum minimum finding. All these topics are discussed in this chapter.

Society for Industrial and Applied Mathematics eBooks•Dec 17, 2025•0 citations

Optimizing Quantum Search with a Binomial Version of Grover's Algorithm

Austin Gilliam, Marco Pistoia, Constantin Gonciulea

Amplitude Amplification -- a key component of Grover's Search algorithm -- uses an iterative approach to systematically increase the probability of one or multiple target states. We present novel strategies to enhance the amplification procedure by partitioning the states into classes, whose probabilities are increased at different levels before or during amplification. The partitioning process is based on the binomial distribution. If the classes to which the search target states belong are known in advance, the number of iterations in the Amplitude Amplification algorithm can be drastically reduced compared to the standard version. In the more likely case in which the relevant classes are not known in advance, their selection can be configured at run time, or a random approach can be employed, similar to classical algorithms such as binary search. In particular, we apply this method in the context of our previously introduced Quantum Dictionary pattern, where keys and values are encoded in two separate registers, and the value-encoding method is independent of the type of superposition used in the key register. We consider this type of structure to be the natural setup for search. We confirm the validity of our new approach through experimental results obtained on real quantum hardware, the Honeywell System Model H0 trapped-ion quantum computer.

arXiv:2007.10894•Jul 21, 2020•1 citation

Amplitude amplification and estimation

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers the quantum algorithmic primitives of amplitude amplification and amplitude estimation. Amplitude amplification is a generalization of Grover’s quantum algorithm for the unstructured search problem. Amplitude estimation can be understood in a similar framework, where it utilizes quantum phase estimation to estimate the value of the amplitude or probability associated with a quantum state. Both amplitude amplification and amplitude estimation provide a quadratic speedup over their classical counterparts, and feature prominently as an ingredient in many end-to-end algorithms.

Cambridge University Press eBooks•Apr 24, 2025•0 citations

The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0

Kamil Ravilevich Khadiev, Ilnaz Mannapov, Liliya Safina

In the paper, we focus on complexity of C5.0 algorithm for constructing decision tree classifier that is the models for the classification problem from machine learning. In classical case the decision tree is constructed in $O(hd(NM+N \log N))$ running time, where $M$ is a number of classes, $N$ is the size of a training data set, $d$ is a number of attributes of each element, $h$ is a tree height. Firstly, we improved the classical version, the running time of the new version is $O(h\cdot d\cdot N\log N)$. Secondly, we suggest a quantum version of this algorithm, which uses quantum subroutines like the amplitude amplification and the D{ü}rr-Høyer minimum search algorithms that are based on Grover's algorithm. The running time of the quantum algorithm is $O\big(h\cdot \sqrt{d}\log d \cdot N \log N\big)$ that is better than complexity of the classical algorithm.

arXiv:1907.06840•Jul 16, 2019•18 citations
Abstract In this work, we present our experiment’s results where we simulate the quantum amplitude amplification algorithm for a prediction problem. The problem is to calculate the total probability of a good class by an ensemble model. Theoretically, the quantum prediction will be quadratically faster than a classical prediction. We need to get outputs (probabilities of the good class) of all classifiers. After that, by summation the probabilities the ensemble model returns the total probability of the good class for an input object. Let us demonstrate how the quantum amplitude amplification algorithm allows us to estimate the total probability. In this experiment, we count an iterations number of quantum search running to estimate the total probability.
In this work, we consider the performance of using a quantum algorithm to predict the result of a binary classification problem when a machine learning model is an ensemble of any simple classifiers. This approach is faster than classical prediction and uses quantum and classical computing, but it is based on a probabilistic algorithm. Let N be the number of classifiers from an ensemble model and O(T) be the running time of prediction of one classifier. In classical case, the final result is obtained by ”averaging” outcomes of all ensemble model’s classifiers. The running time in classical case is O (N · T). We propose an algorithm that works in O (√N · T ).
In this work, we conducted an experiment on a quantum simulator for tasks of binary classification by the random forest method, estimated the time the complexity of the classical and quantum versions of the algorithms, as well as memory complexity of the algorithm for the quantum version. Previously we received temporal acceleration of the algorithm for prediction by using quantum amplitude amplification algorithm, and now tested the algorithm proposed by us on our quantum simulator and analyzed the predictive results.
In Chs. 2 and 3 we described several quantum algorithms that are exponentially faster than classical algorithms for the same problem, under some measure of complexity. Unfortunately, the algorithms of Ch. 2 apply to rather contrived problems that do not have known direct applications. We now describe a quantum algorithm that gives only a polynomial—more specifically, quadratic—speedup with respect to classical algorithms, but it applies to a large class of problems and finds many useful applications, both directly and as an algorithmic design tool. The algorithm is known as Grover’s search [89], and its generalization is known as amplitude amplification [43]. Amplitude amplification is widely used as part of many quantum algorithms. It also serves as the basis for amplitude estimation, a way of estimating probabilities quadratically faster than with classical Monte Carlo, and for quantum minimum finding. All these topics are discussed in this chapter.
Amplitude Amplification -- a key component of Grover's Search algorithm -- uses an iterative approach to systematically increase the probability of one or multiple target states. We present novel strategies to enhance the amplification procedure by partitioning the states into classes, whose probabilities are increased at different levels before or during amplification. The partitioning process is based on the binomial distribution. If the classes to which the search target states belong are known in advance, the number of iterations in the Amplitude Amplification algorithm can be drastically reduced compared to the standard version. In the more likely case in which the relevant classes are not known in advance, their selection can be configured at run time, or a random approach can be employed, similar to classical algorithms such as binary search. In particular, we apply this method in the context of our previously introduced Quantum Dictionary pattern, where keys and values are encoded in two separate registers, and the value-encoding method is independent of the type of superposition used in the key register. We consider this type of structure to be the natural setup for search. We confirm the validity of our new approach through experimental results obtained on real quantum hardware, the Honeywell System Model H0 trapped-ion quantum computer.
This chapter covers the quantum algorithmic primitives of amplitude amplification and amplitude estimation. Amplitude amplification is a generalization of Grover’s quantum algorithm for the unstructured search problem. Amplitude estimation can be understood in a similar framework, where it utilizes quantum phase estimation to estimate the value of the amplitude or probability associated with a quantum state. Both amplitude amplification and amplitude estimation provide a quadratic speedup over their classical counterparts, and feature prominently as an ingredient in many end-to-end algorithms.
In the paper, we focus on complexity of C5.0 algorithm for constructing decision tree classifier that is the models for the classification problem from machine learning. In classical case the decision tree is constructed in O(hd(NM+Nlog⁡N))O(hd(NM+N \log N))O(hd(NM+NlogN)) running time, where MMM is a number of classes, NNN is the size of a training data set, ddd is a number of attributes of each element, hhh is a tree height. Firstly, we improved the classical version, the running time of the new version is O(h⋅d⋅Nlog⁡N)O(h\cdot d\cdot N\log N)O(h⋅d⋅NlogN). Secondly, we suggest a quantum version of this algorithm, which uses quantum subroutines like the amplitude amplification and the D{ü}rr-Høyer minimum search algorithms that are based on Grover's algorithm. The running time of the quantum algorithm is O(h⋅dlog⁡d⋅Nlog⁡N)O\big(h\cdot \sqrt{d}\log d \cdot N \log N\big)O(h⋅d​logd⋅NlogN) that is better than complexity of the classical algorithm.