Summary#
As part of my final year at university, I undertook a substantial research project titled “Using Quantum Annealing to Solve the Elliptic Subset Sum Problem”.
My project proposes two methods to solve certain instances of the Elliptic Subset Sum Problem. This is a variation of the subset sum problem which uses rational points on elliptic curves instead of integers.
The methods proposed use quantum annealing which is a form of adiabatic quantum computation. Solving a problem using quantum annealing involves reformulating the problem instance as an instance of the Ising Model or a Quadratic Unconstrained Binary Optimisation (QUBO) problem. This is something that can be done quite easily for the integer subset sum problem, but is very difficult when considering rational points on elliptic curves due to their non-linear addition rule. In other words, the project’s challenge comes from the fact that the mathematical structure of these elliptic curve points makes it much more difficult to express the problem in a way that a quantum annealer can work with.
Whilst the subset sum problem itself does not have many practical applications, elliptic curves certainly do, especially in cryptography. Researchers interested in post-quantum cryptography have recently tried to use quantum annealing in order to solve the elliptic discrete logarithm problem, i.e. the discrete logarithm problem using rational points on elliptic curves. My project attempts to use insights gathered by these attempts in order to solve a different computational problem, which still involves elliptic curves.
My project discusses two potential methods of applying quantum annealing to the elliptic subset sum problem and proves their theoretical correctness. It also uses experimentation in order to demonstrate the practical limitations of these methods.
The full report, including scripts used to carry out the aforementioned experiments, are available in the git repository linked below.