Quantum Solutions to Difficult Problems

Srinivas Sridharan, Mile Gu, M. R. James +1 more

Although quantum computers have the potential to efficiently solve certain problems considered difficult by known classical approaches, the design of a quantum circuit remains computationally difficult. It is known that the optimal gate-design problem is equivalent to the solution of an associated optimal-control problem; the solution to which is also computationally intensive. Hence, in this article, we introduce the application of a class of numerical methods (termed the max-plus curse of dimensionality-free techniques) that determine the optimal control, thereby synthesizing the desired unitary gate. The application of this technique to quantum systems has a growth in complexity that depends on the cardinality of the control-set approximation rather than the much larger growth with respect to spatial dimensions in approaches based on gridding of the space, which is used in previous research. This technique is demonstrated by obtaining an approximate solution for the gate synthesis on SU(4)---a problem that is computationally intractable by grid-based approaches.

Flavio Jesus de Souza, Flávio Luís de Mello

This paper aims to propose solution for a classical and difficult decision problem using quantum computing. At first, it provides experimental samples taking well-known search problems, where it is possible to establish a plausible comparison between classical search algorithms and a similar quantum algorithm. Moreover, a quantum algorithm is construct in order to deliver solution for a sophisticated mathematical problem called N-Queens. The algorithm was implemented in a quantum computing simulator obtaining solutions for problems with up to 128 queens at a reasonable cost.

Alexei Petrenko, Sergei Petrenko

Purpose of the article: development of quantum algorithms for efficient solution of cryptanalysis problems of asymmetric encryption schemes (RSA, ElGamal) and digital signature (DSA, ECDSA or RSA-PSS), based on computationally difficult problems of factorization and discrete logarithm.Research methods: Methods of quantum cryptanalysis based on the algorithms of Shor, Grover, Simon, etc.Results: algorithms for solving problems of quantum cryptanalysis of two-key cryptography schemes in polynomial time.Practical relevance: consists in developing a solution for computationally difficult problems of factorization and discrete logarithm in polynomial time, taking into account the security of the discrete algorithm (DLP) and the discrete elliptic curve algorithm (ECDLP). The obtained scientific results formed the basis for the development of a special Software Development Kit, SDK for cryptanalysis “Kvant-K”. The Certificate of state registration of the computer program No. 2020665981 was received.

Jozef Gruska