Kamil Khadiev

Kamil Khadiev, Ilnur Valeev

We present a quantum circuit implementation of the quantum hashing algorithm (quantum fingerprinting) for a quantum device with restrictions on the application of two-qubit gates by a qubit connectivity graph. We present an optimization technique for the shallow circuit for quantum hashing in the case of a cactus as a qubit connectivity graph. The algorithm has $O(n^3)$ complexity to build the circuit, where $n$ is the number of qubits and $m$ is the number of connections (edges) in the graph. It is improvement compared to the existing exponential-time algorithm in the case of arbitrary graphs. The algorithm uses solution for the shortest non-simple 1-covering path problem as a subroutine. We present an $O(n^3)$-time solution for this graph-theory problem in the case of a cactus. This result can be interesting independently. The algorithm also used for improving of the quantum circuit for Quantum Fourier Transform.

Kamil Khadiev, Liliya Safina

The Random Forest model is one of the popular models of Machine learning. We present a quantum algorithm for testing (forecasting) process of the Random Forest machine learning model for the Regression problem. The presented algorithm is more efficient (in terms of query complexity or running time) than the classical counterpart.

Kamil Khadiev, Liliia Safina

In this work, we consider the performance of using a quantum algorithm to predict a result for a binary classification problem if a machine learning model is an ensemble from any simple classifiers. Such an approach is faster than classical prediction and uses quantum and classical computing, but it is based on a probabilistic algorithm. Let $N$ be a number of classifiers from an ensemble model and $O(T)$ be the running time of prediction on one classifier. In classical case, an ensemble model gets answers from each classifier and "averages" the result. The running time in classical case is $O\left( N \cdot T \right)$. We propose an algorithm which works in $O\left(\sqrt{N} \cdot T\right)$.

Kamil Khadiev, Carlos Manuel Bosch Machado

In this paper, we consider the ``Shortest Superstring Problem''(SSP) or the ``Shortest Common Superstring Problem''(SCS). The problem is as follows. For a positive integer $n$, a sequence of n strings $S=(s^1,\dots,s^n)$ is given. We should construct the shortest string $t$ (we call it superstring) that contains each string from the given sequence as a substring. The problem is connected with the sequence assembly method for reconstructing a long DNA sequence from small fragments. We present a quantum algorithm with running time $O^*(1.728^n)$. Here $O^*$ notation does not consider polynomials of $n$ and the length of $t$.

Kamil 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.