Quantum Learning Algorithms: Progress and Challenges in Solving Cryptographic Problems from Korean Researchers

Quantum learning algorithms, a rapidly growing field in quantum technology, have shown success in solving noisy linear problems relevant to cryptographic hard problems. In 2019, researchers Grilo et al. proved that the Learning with Errors (LWE) problem could be solved using the Bernstein-Vazirani (BV) algorithm.

However, the development and improvement of these algorithms involve examining underlying assumptions, such as the controversial quantum random access memory (QRAM). In 2022, Grilo et al.’s algorithm was revised using a divide-and-conquer strategy, leading to a new quantum learning algorithm for the Ring Learning with Errors (RLWE) problem. Despite promising results, the future of quantum learning algorithms remains uncertain due to challenges and controversies.

What are Quantum Learning Algorithms for Noisy Linear Problems?

Quantum learning algorithms are a rapidly growing field in quantum technology, particularly in machine learning. These algorithms have successfully solved noisy linear problems with quantum samples, which are relevant to cryptographic hard problems. In this context, a noisy linear problem refers to a mathematical problem in which the input data is affected by noise or error. Quantum learning algorithms are designed to solve these problems even when the data is imperfect.

In 2019, a significant milestone was achieved by researchers Grilo et al., who proved that the Learning with Errors (LWE) problem could be efficiently solved using the Bernstein-Vazirani (BV) algorithm, provided a certain form of a superposed data sample is available. The LWE problem is a common problem in cryptography, where the goal is to find a secret vector given a set of linear equations with noisy solutions. The BV algorithm is a quantum algorithm that extracts information from a black box function.

How are Quantum Learning Algorithms Developed and Improved?

The development and improvement of quantum learning algorithms involve a careful examination of underlying assumptions and their plausibility. For instance, the assumption of quantum random access memory (QRAM) has been a center of controversies in the study of quantum algorithms. QRAM is a theoretical model of how quantum computers would access classical data, but the requirement of exponentially many qubits has hindered its realization.

In 2022, the algorithm by Grilo et al. was further revised by utilizing a divide-and-conquer strategy, which deals with component-wise problems. However, the authors noted that their LWE algorithm could not be extended to solve Ring Learning with Errors (RLWE) problems, which are a variant of the LWE problem. This led to the development of a new quantum learning algorithm for the RLWE problem.

What are the Challenges and Concerns in Quantum Learning Algorithms?

One of the main challenges in quantum learning algorithms is the plausibility of certain assumptions. For instance, the assumption of a quantum sample in the Short Integer Solution (SIS) problem is considered less plausible than that in the LWE problem. The SIS problem is another cryptographic hard problem, where the goal is to find a short non-zero integer vector in the lattice defined by a given matrix.

Moreover, the practicality of size-reduced quantum samples, as suggested by the divide-and-conquer algorithm, has been questioned. Given the same samples, there exist polynomial-time classical algorithms for the LWE problem, which are more efficient than the corresponding quantum algorithms.

How are Quantum Learning Algorithms Evaluated?

The evaluation of quantum learning algorithms involves a thorough examination of their assumptions and the feasibility of their solutions. For instance, the claim by Grilo et al. that their LWE algorithm cannot be extended to solve RLWE problems was examined, leading to a solution and a new quantum learning algorithm for the RLWE problem.

Similarly, the claim that the SIS problem can be solved by the learning algorithm with quantum samples was reexamined. It was found that given the SIS sample introduced by the authors, there exists a polynomial-time classical algorithm for the SIS problem.

What is the Future of Quantum Learning Algorithms?

The future of quantum learning algorithms is still uncertain. While these algorithms have shown promising results in solving cryptographic hard problems, there are still many challenges and controversies to be addressed. For instance, it is not clear how a quantum sample can be prepared for these algorithms, and there is no mathematical proof that an efficient way of obtaining quantum samples is possible.

However, the rapid growth of the field and the continuous development and improvement of these algorithms suggest a promising future. As researchers continue to examine and evaluate these algorithms, new solutions and algorithms are likely to be developed, further advancing the field of quantum learning algorithms.