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

Physics

Making Hard Problems for Quantum Computers

Anonymous

Published Jul 14, 2016• 0 citations
Publisher
DOI
10.1103/physics.9.s77

Related papers

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

Solving mathematical problems with quantum computers

배준우

•May 23, 2019•0 citations

Quantum Reductions from Hard problems

Nai-Hui Chia

•Apr 2, 2018•0 citations

Cryptographic Protocols Resilient to Quantum Attacks: Advancements in Post-Quantum Cryptography

Pallavi Niraj Vithalkar

New developments in quantum computing have made people worry that current security methods could be broken by quantum attacks. Some mathematical problems are hard to solve, which is how traditional encryption methods like RSA and ECC keep their secrets safe. However, quantum computers might be able to solve these issues a lot faster than regular computers, which makes these methods less safe. Because of this threat, experts have been working hard to make post-quantum cryptography methods that quantum computers can't break. These methods are made to stand up to the strength of quantum algorithms and protect the privacy, integrity, and validity of private data even when quantum attackers are present. Lattice-based cryptography is a potential method for post-quantum encryption. Its security comes from the difficulty of certain lattice problems. Lattice-based methods are thought to be safe from threats from both traditional and quantum computers because they offer good security promises. Lattice-based cryptography is a flexible way to build different types of cryptographic primitives, like encryption, digital signatures, and key sharing protocols. The study of code-based cryptography, which is based on how hard it is to decode some error-correcting codes, is another important advance. Code-based methods have been around for a long time and have been studied a lot, which makes them a good choice for security after quantum computing. Code-based cryptography is also easy to use and has strong security features, which makes it a good choice for real-world situations. Multivariate polynomial cryptography is another possible choice for cryptography after quantum computing. The safety of this method depends on how hard it is to solve systems of multivariate polynomial problems. Multivariate polynomial methods might not be as secure as lattice-based or code-based cryptography, but they are interesting options for some situations and places with limited resources.

Communications on Applied Nonlinear Analysis•Jun 23, 2024•6 citations

Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem

Sébastien Perseguers

We propose a numerical approach to design highly efficient adiabatic schedules for analog quantum computing, focusing on the maximum-independent-set problem and neutral atom platforms. On the basis of a representative dataset of small graphs, we present numerical evidence that the optimum schedules depend principally on the hardness of the problem rather than on its size. These schedules perform better than the benchmark protocols and admit a straightforward implementation in the hardware. This allows us to extrapolate the results to larger graphs and to successfully solve moderately hard problems using QuEra’s 256-qubit Aquila computer. We believe that extending our approach to hybrid algorithms could be the key to solving the hardest instances with the current technology, making yet another step toward real-world applications.

arXiv:2410.08995•Physical Review Applied•Jun 10, 2025•6 citations

Problem-solving and Quantum Computation

Luís Domingues Tomé Jardim Tarrataca, Andreas Wichert

Cognitive Computation•Jun 30, 2011•10 citations
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.
New developments in quantum computing have made people worry that current security methods could be broken by quantum attacks. Some mathematical problems are hard to solve, which is how traditional encryption methods like RSA and ECC keep their secrets safe. However, quantum computers might be able to solve these issues a lot faster than regular computers, which makes these methods less safe. Because of this threat, experts have been working hard to make post-quantum cryptography methods that quantum computers can't break. These methods are made to stand up to the strength of quantum algorithms and protect the privacy, integrity, and validity of private data even when quantum attackers are present. Lattice-based cryptography is a potential method for post-quantum encryption. Its security comes from the difficulty of certain lattice problems. Lattice-based methods are thought to be safe from threats from both traditional and quantum computers because they offer good security promises. Lattice-based cryptography is a flexible way to build different types of cryptographic primitives, like encryption, digital signatures, and key sharing protocols. The study of code-based cryptography, which is based on how hard it is to decode some error-correcting codes, is another important advance. Code-based methods have been around for a long time and have been studied a lot, which makes them a good choice for security after quantum computing. Code-based cryptography is also easy to use and has strong security features, which makes it a good choice for real-world situations. Multivariate polynomial cryptography is another possible choice for cryptography after quantum computing. The safety of this method depends on how hard it is to solve systems of multivariate polynomial problems. Multivariate polynomial methods might not be as secure as lattice-based or code-based cryptography, but they are interesting options for some situations and places with limited resources.
We propose a numerical approach to design highly efficient adiabatic schedules for analog quantum computing, focusing on the maximum-independent-set problem and neutral atom platforms. On the basis of a representative dataset of small graphs, we present numerical evidence that the optimum schedules depend principally on the hardness of the problem rather than on its size. These schedules perform better than the benchmark protocols and admit a straightforward implementation in the hardware. This allows us to extrapolate the results to larger graphs and to successfully solve moderately hard problems using QuEra’s 256-qubit Aquila computer. We believe that extending our approach to hybrid algorithms could be the key to solving the hardest instances with the current technology, making yet another step toward real-world applications.