Quantum Reductions from Hard problems

Open Access
Author:
Chia, Nai Hui
Graduate Program:
Computer Science and Engineering
Degree:
Doctor of Philosophy
Document Type:
Dissertation
Date of Defense:
April 02, 2018
Committee Members:
  • Sean Hallgren, Dissertation Advisor
  • Sean Hallgren, Committee Chair
  • Daniel Kifer, Committee Member
  • Martin Furer, Committee Member
  • Jason Ryder Morton, Outside Member
Keywords:
  • quantum comoutation
  • cryptographically primitives
  • dihedral coset problem
  • worst-case to average-case reduction
  • quantum interactive proof
  • subset sum problem
Abstract:
Finding reductions between problems is a fundamental way to evaluate hardness of computational tasks. With hypothesis in complexity theory such as $NP\neq P$, finding reductions from hard problems (e.g. SAT) to a task implies the task cannot be accomplished efficiently. For example, if one can find a reduction from SAT to breaking a cryptosystem, then this cryptosystem is computationally secure unless $NP=P$. On the other hand, for some tasks, it can be proven that hard problems cannot reduce to them. For instance, the existence of reductions from SAT to finding Nash equilibrium results in the consequence that polynomial hierarchy collapses. This can view as evidence that finding the Nash equilibrium can not be as hard as NP-hard problems. There are many similar results studying classical reductions (which are either deterministic or randomized) between hard problems and tasks which have interesting applications. However, for quantum reductions, there are not many known examples. Quantum algorithms are believed to be more powerful than classical algorithms. Therefore, intuitively, we ask: Can we find quantum reductions between problems, where no classical reduction is known? Or, given a task, can we rule out the possibility that there are hard problems reducing to the task via quantum reductions? In this thesis, we study quantum reductions in these two directions. For the first topic, we study the dihedral hidden subgroup problem by relating its hardness to a well-studied classical problem, the random subset sum problem. The dihedral hidden subgroup is an important open problem in quantum computing and cryptography. It is known that lattice problems reduce to it, and that it reduces to random subset sum with density $> 1$ and also to quantum sampling subset sum solutions. We examine a decision version of the problem where the question asks whether the hidden subgroup is trivial or order two. The decision problem essentially asks if a given vector is in the span of all coset states. We approach this by first computing an explicit basis for the coset space and the perpendicular space. We then look at the consequences of having efficient unitaries that use this basis. We show that if a unitary maps the basis to the standard basis in any way, then that unitary can be used to solve random subset sum with constant density $>1$. We also show that if a unitary can exactly decide membership in the coset subspace, then the collision problem for subset sum can be solved for density $>1$ but approaching $1$ as the problem size increases. This strengthens the previous hardness result that implementing the optimal POVM in a specific way is as hard as quantum sampling subset sum solutions. For the second topic, we consider whether quantum reductions from NP-hard problems to breaking cryptosystem exist. In cryptography, it requires a system to be hard to be broken on average instead of being hard in the worst case. To show the security of a cryptosystem, one ideal approach is reducing a worst-case hard problem to breaking the system on average. Therefore, reducing NP-hard problems to breaking cryptography, e.g., the average-case hardness of inverting one-way permutations is a particularly intriguing instance. We initiate a study of the quantum analogue of these questions and show that if NP-complete problems can be reduced to inverting one-way permutations using certain types of quantum reductions, then coNP $\subseteq$ QIP(2).