Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Reductions from Hard problems

Nai-Hui Chia

Published Apr 2, 2018• 0 citations
OpenAlex

Related papers

Making Hard Problems for Quantum Computers

Anonymous

Physics•Jul 14, 2016•0 citations

On Basing One-way Permutations on NP-hard Problems under Quantum Reductions

Nai-Hui Chia, Sean Hallgren, Fang Song

A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then coNP ⊆ QIP( 2 ) .

arXiv:1804.10309•Quantum•Aug 27, 2020•3 citations

Tighter Reductions of LWE Problems with Semi-uniform Seeds

Wang Yang, Wang Mingqiang

In certain designs and applications of practical lattice-based cryptography, the use of a specialized variant of LWE problems, where the public matrix is sampled from a non-uniform distribution, is required to establish the security of the corresponding cryptographic schemes. Recently, the formal definition of LWE problems with semi-uniform seeds was introduced by the community, in which the hardness of Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds was proved through reduction approach similar to those employed in the hardness proofs of entropic LWE problems. However, known reduction introduces significant losses in the Gaussian error parameters and lattice dimensions. Moreover, additional non-standard assumptions are required to demonstrate the hardness of LWE problems with semi-uniform seeds over rings. In this paper, a tighter reduction is proposed for LWE problems with semi-uniform seeds by incorporating modified techniques from the hardness proofs of Hint-LWE problems. The proposed reduction is unaffected by the algebraic structure of the underlying problems and can be uniformly applied to Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds. The hardness of these LWE problems can be established based on standard LWE assumptions without the need for any additional non-standard assumption. Furthermore, the dimension of corresponding LWE problems remains unchanged, and the reduction introduces only minimal losses in Gaussian error parameters.

International Journal of Software and Informatics•Jan 1, 2025•0 citations

Turning Hard Problems into Post-quantum Solutions

Gretchen L. Matthews

American Scientist•Jan 1, 2024•0 citations

Average-case hardness of Betti number estimation

Sergii Strelchuk, Sathyawageeswar Subramanian, Adam Wesołowski

We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis (qTDA). Under the classical planted clique conjecture, no randomized polynomial-time Betti number estimator achieves additive error below $\tfrac12$ with constant advantage. Under a new quantum planted clique conjecture that we introduce, the same conclusion holds for quantum polynomial-time algorithms. We also obtain related conditional hardness results for homology vanishing, additive approximations with larger error tolerances, preparation of simplex and harmonic states, cycle recovery, and counting eigenvalues at low energy. Our reduction clarifies the structural requirements for quantum advantage in TDA and provides a new lens to investigate the classical and quantum complexity of related problems.

quant-pharXiv:2609.12777•Sep 14, 2026•2 citations

Hardness of Lattice Based Cryptography

Thor Tunge

In this thesis we will discuss hard computational problems in lattice theory and relate them to cryptographic constructions. Many of these problems enjoy average-case hardness which makes them attractive for cryptography. In addition, lattice based cryptography is a candidate for post-quantum cryptography, as there is no known quantum algorithm which breaks various hardness theorems.\n\nWe build a foundation in algebraic number theory to have the required background to discuss schemes based on discrete algebraic structures. These structures are free Z-modules which permits unique factorization in prime ideals. We relate this algebraic number theory to lattices in R^n so we can use the theory from algebra to our advantage.\n\nWe then define some standard hard computational lattice problems and show how many of these are related to each other. We prove that these problems are at least as hard as finding the shortest vector of a lattice, which we conjecture is computationally infeasible. We then prove a quantum reduction the learning with errors problem, a problem in machine learning . We also show that there is a similar reduction for a variant of this problem over more general rings.

•Jan 1, 2018•0 citations
A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then coNP ⊆ QIP( 2 ) .
In certain designs and applications of practical lattice-based cryptography, the use of a specialized variant of LWE problems, where the public matrix is sampled from a non-uniform distribution, is required to establish the security of the corresponding cryptographic schemes. Recently, the formal definition of LWE problems with semi-uniform seeds was introduced by the community, in which the hardness of Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds was proved through reduction approach similar to those employed in the hardness proofs of entropic LWE problems. However, known reduction introduces significant losses in the Gaussian error parameters and lattice dimensions. Moreover, additional non-standard assumptions are required to demonstrate the hardness of LWE problems with semi-uniform seeds over rings. In this paper, a tighter reduction is proposed for LWE problems with semi-uniform seeds by incorporating modified techniques from the hardness proofs of Hint-LWE problems. The proposed reduction is unaffected by the algebraic structure of the underlying problems and can be uniformly applied to Euclidean, ideal, and module lattice-based LWE problems with semi-uniform seeds. The hardness of these LWE problems can be established based on standard LWE assumptions without the need for any additional non-standard assumption. Furthermore, the dimension of corresponding LWE problems remains unchanged, and the reduction introduces only minimal losses in Gaussian error parameters.
We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis (qTDA). Under the classical planted clique conjecture, no randomized polynomial-time Betti number estimator achieves additive error below 12\tfrac1221​ with constant advantage. Under a new quantum planted clique conjecture that we introduce, the same conclusion holds for quantum polynomial-time algorithms. We also obtain related conditional hardness results for homology vanishing, additive approximations with larger error tolerances, preparation of simplex and harmonic states, cycle recovery, and counting eigenvalues at low energy. Our reduction clarifies the structural requirements for quantum advantage in TDA and provides a new lens to investigate the classical and quantum complexity of related problems.
In this thesis we will discuss hard computational problems in lattice theory and relate them to cryptographic constructions. Many of these problems enjoy average-case hardness which makes them attractive for cryptography. In addition, lattice based cryptography is a candidate for post-quantum cryptography, as there is no known quantum algorithm which breaks various hardness theorems.\n\nWe build a foundation in algebraic number theory to have the required background to discuss schemes based on discrete algebraic structures. These structures are free Z-modules which permits unique factorization in prime ideals. We relate this algebraic number theory to lattices in R^n so we can use the theory from algebra to our advantage.\n\nWe then define some standard hard computational lattice problems and show how many of these are related to each other. We prove that these problems are at least as hard as finding the shortest vector of a lattice, which we conjecture is computationally infeasible. We then prove a quantum reduction the learning with errors problem, a problem in machine learning . We also show that there is a similar reduction for a variant of this problem over more general rings.