The subset cover problem for
k≥1 hash functions, which can be seen as an extension of the collision problem, was introduced in 2002 by Reyzin and Reyzin to analyse the security of their hash-function based signature scheme HORS. The security of many hash-based signature schemes relies on this problem or a variant of this problem (e.g. HORS, SPHINCS, SPHINCS+,
…). Recently, Yuan, Tibouchi and Abe (2022) introduced a variant to the subset cover problem, called restricted subset cover, and proposed a quantum algorithm for this problem. In this work, we prove that any quantum algorithm needs to make
Ω((k+1)−2k+1−12k⋅N2k+1−12k−1) queries to the underlying hash functions with codomain size
N to solve the restricted subset cover problem, which essentially matches the query complexity of the algorithm proposed by Yuan, Tibouchi and Abe. We also analyze the security of the general
(r,k)-subset cover problem, which is the underlying problem that implies the unforgeability of HORS under a
r-chosen message attack (for
r≥1). We prove that a generic quantum algorithm needs to make
Ω(Nk/5) queries to the underlying hash functions to find a
(1,k)-subset cover. We also propose a quantum algorithm that finds a
(r,k)-subset cover making
O(Nk/(2+2r)) queries to the
k hash functions.
We show that the quantum smooth label cover problem is undecidable and RE-hard. This sharply contrasts the quantum unique label cover problem, which can be decided efficiently by a result of Kempe, Regev, and Toner (FOCS'08). On the other hand, our result aligns with the RE-hardness of the quantum label cover problem, which follows from the celebrated MIP* = RE result of Ji, Natarajan, Vidick, Wright, and Yuen (ACM'21). Additionally, we show that the quantum oracularized smooth label cover problem is RE-hard. Our second result fits with the alternative quantum unique games conjecture recently proposed by Mousavi and Spirig (ITCS'25) on the RE-hardness of the quantum oracularized unique label cover problem. Our proof techniques include a quantum version of Feige's reduction from 3SAT to 3SAT5 (STOC'96) for BCSMIP*-protocols, which may be of independent interest.
Quantum annealing (QA) uses the principles of quantum mechanics for solving unconstrained optimization problems. Since its initial proposal, there has been much interest in the search for practical problems for which QA has advantage over classical algorithms. Although it is believed that quantum computers cannot in general solve NP-complete problems efficiently, there has been evidence suggesting that effects such as quantum tunneling can bring quantum speedup over classical computation for some problems in NP. In this dissertation, we consider two problems that have both theoretical and practical importance. One is the Set Cover with Pairs problem. The other is the Factorization problem. The Set Cover with Pairs (SCP) problem is a generalization of the Set Cover problem. It requires each element in a set to be covered by at least two objects instead of one as in the Set Cover problem. The SCP problem is believed to be not only NP-hard, but also hard to approximate. In this dissertation, we explicitly construct the Ising Hamiltonians whose ground states encode the solutions of SCP instances. The resulting Ising Hamiltonian has the appealing property that the control precision required for encoding an SCP instance scales only linearly with the number of objects in the covering set. The Integer Factorization problem is of great interest in the quantum community because it is difficult to solve using classical methods and its importance in cryptography. In this dissertation, we propose a general framework for solving factorization problems using quantum annealing, by mapping the framework to an Ising Hamiltonian. We develop several methods to consider the specific requirements such as control precision, spin-spin connection in the current Ising machines. We test the methods on the latest D-Wave 2000Q machine.