Quantum computation is a new information processing paradigm, which promises to solve particular classes of tasks faster comparing to conventional (classical) computers. The best-known example is the Shor algorithm, which solves the integer factorization problem in polynomial time. The best known classical algorithms require exponential time in the number's length. However, even if Shor's algorithm requires a polynomial number of qubits and quantum gates only, this is beyond the capabilities of current quantum computers. There are two main reasons. First, quantum computers still make computation imperfectly. Second, current quantum computers operate on a small number of qubits. It is expected that quantum computers in the near future will be limited by those two factors as well, as thus currently available devices are commonly described as Noisy Intermediate-Scale Quantum (NISQ) computers. To overcome the limitations of this technology, a considerable research effort has been put towards formulating computational problems in the form suitable for executing on NISQ devices.

The main framework developed for currently available quantum computers is known as \emph{variational quantum computing}. In this approach, first we encode the problem into a quantum Hamiltonian, and then optimize the quantum state using classical optimization techniques to find the optimum of the original problem. It is believed that the method is useful for finding physical states with the lowest energy given some energy description of the chemical system, the application which is exciting from the perspective of chemistry and material sciences. However, while this method is useful for generating the solution for quantum-oriented problem instances, it is not evident whether the algorithms based on variational quantum computing could solve efficiently the problems appearing in classical computer science.

The reason is similar as in the case of the Shor algorithm. While variational quantum computing paradigm is much less demanding in term of quantum resources, still only small instances can be considered. As an example, consider the famous Travelling Salesman Problem, which aims at finding optimal, usually the shortest, route passing through all cities. Current classical algorithms can solve the problem optimally even for thousands of cities. Unfortunately, state-of-the-art variational quantum computing methods we are limited to at most 8 cities for currently the biggest, 53-qubit large quantum computer. Such instances can be in practice solved even by checking each possible route and choosing the best one.

We claim that the reason behind this comes from the waste of quantum memory sources. The project will focus on designing more efficient encodings, which will able quantum computers tackling much larger instances than currently used. Thanks to that, we will make a one step forward to showing a quantum computational advantage.