Quantum Algorithms for Solving Polynomial Systems and Pathfinding Problems with Potential Superpolynomial Speedups
Open Access
- Author:
- Li, Jianqiang
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- October 07, 2024
- Committee Members:
- Chitaranjan Das, Program Head/Chair
Martin Fürer, Major Field Member
Antonio Blanca, Major Field Member
Chunhao Wang, Major Field Member
Jason Morton, Outside Unit & Field Member
Sean Hallgren, Chair & Dissertation Advisor - Keywords:
- Quantum speedups
Quantum linear system algorithm
Polynomial systems
Multidimensional electrical network
Adjacency matrix - Abstract:
- Finding problems in which quantum algorithms can provide superpolynomial speedup is one of the most challenging tasks in quantum computation. The challenges come from identifying problems that can only be exploited by quantum mechanics. In this thesis, we explore two such problems that have the potential to allow superpolynomial quantum speedup. One is to find a root of a multivariate polynomial system; the other is to find an s-t path in certain types of graphs of exponential size. The security of two types of postquantum cryptosystems, multivariate-based cryptography, and isogeny-based cryptography, depends on the difficulty of solving some instances of those two problems. These two problems are widely believed to be classically hard, while not enough quantum cryptoanalysis has been done. For the problem of solving a system of polynomial equations, we have shown the limitations and potentials of a particular approach to show the superpolynomial quantum speed-up. The problem of finding a root of a multivariate polynomial system can be reduced to solving an exponentially large linear system. The Quantum Linear System (QLS) algorithm is well known for solving exponentially large quantum linear systems. Using the connection between the linear system and the QLS algorithm, Chen and Gao map the problem of finding a root of a polynomial system to a quantum algorithm, but the running time of their algorithm was unknown. We showed the limitations of the quantum algorithm by proving a lower bound on its running time and showed that the Grover search outperforms this algorithm in many cases. Then we improve the algorithm by running the QLS algorithm on a smaller linear system so that it has the potential to exhibit a superpolynomial speedup for some special polynomial systems. For the problem of finding an s-t path in graphs of exponential size, we have shown exponential quantum speedups on three families of graphs in the adjacency list oracle, namely the welded tree path graph, the welded tree circuit graph, and the regular sunflower graph. The welded tree path graph is a non-regular graph, and the quantum algorithm uses the degree information to efficiently find an s-t path. The welded tree circuit graph is a regular graph, and a newly developed multidimensional electrical network framework is used to generate a quantum superposition state over the edges of the graph to efficiently find an s-t path. The regular sunflower graph shares structures and expansion properties similar to supersingular isogeny graphs. The quantum algorithm utilizes the $0$-eigenspace of the adjacency matrix of the regular sunflower graph to create a quantum superposition on the vertices of the graph, enabling efficient pathfinding. These exponential speedups shed light on pathfinding in supersingular isogeny graphs, a cornerstone for isogeny-based cryptosystems, and welded tree graphs, a key challenge in quantum query complexity.