Relevant Quantum Algorithms

Song Yuan Yan

Владик Крейнович, Martine C. Ceberio, Ricardo O. de Alba Alvarez

One of the main reasons why computations - in particular, engineering computations - take long is that, to be on the safe side, models take into account all possible affecting features, most of which turn out to be not really relevant for the corresponding physical problem. From this viewpoint, it is desirable to find out which inputs are relevant. In general, the problem of checking the input's relevancy is itself NP-hard, which means, crudely speaking, that no feasible algorithm can always solve it. Thus, it is desirable to speed up this checking as much as possible. One possible way to speed up such a checking is to use quantum computing, namely, to use the Deutsch-Josza algorithm. However, it is not clear whether a more efficient quantum algorithm is possible for solving this problem. In this paper, we show that the Deutsch-Josza algorithm is, in effect, the only possible way to use quantum computing for checking which inputs are relevant - so no alternative quantum algorithms are possible.

Melinda Andrews, Joseph Stephen Dulny, Andrew N. Glaudell +6 more

Jincheng Zhang

Quantum algorithm optimization is a crucial field, demanding efficient and accurate solutions to complex quantum computations. Traditional optimization methods often struggle with the inherent complexities of quantum systems. This paper proposes a novel approach leveraging Gaussian Self-Relevant Graphs (GSRs) to enhance quantum algorithm optimization. We introduce a new optimization algorithm that utilizes GSRs to capture and exploit quantum system dependencies, thereby improving algorithm efficiency and accuracy. The paper details the implementation of the GSR-based optimization algorithm, demonstrates its performance improvements through theoretical analysis and experimental validation, and discusses its potential impact on the future of quantum computing.

Mahn‐Soo Choi

Горбенко, Юрій Іванович, Акользіна, Ольга Сергіївна, Подгайко, Владислав Олегович

An analysis of current research on cryptography on lattices is given. The analysis takes place in accordance with the most relevant algorithms that have gone through the second stage of the US NIST competition. Some of them are combined — include several similar algorithms from the past stage. For a detailed consideration of them, a number of relevant topics for post-quantum algorithms are presented, which allows them to be described and categorized more substantially