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

Futurum Careers

Why is it hard to build quantum computers?

Salini Karuvade

Published Jan 1, 2024• 0 citations
Publisher
DOI
10.33424/futurum525

Related papers

On the Cryptographic Foundations of Interactive Quantum Advantage

Kabir Tomer, Mark Zhandry

In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A “trivial” or non-interactive PoQ simply assumes an (efficiently-verifiable) average-case hard problem for classical computers that is easy for quantum computers. However, there is much interest in “non-trivial” PoQs that actually rely on quantum hardness assumptions, instead of an assumed separation between quantum and classical computation for search problems, especially since these are often a starting point for more sophisticated protocols such as classical verification of quantum computation (CVQC). We show several lower-bounds for the hardness required to achieve non-trivial PoQ, specifically showing that they likely require cryptographic hardness, with different types of cryptographic hardness being required for different variations of non-trivial PoQ. In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ and its various extensions such as CVQC.

arXiv:2510.05082•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•4 citations

What Makes Quantum Computing So Hard to Explain?

Scott Aaronson

Springer eBooks•Jan 1, 2023•5 citations

Will We Ever Have a Quantum Computer?

M. I. Dyakonov

SpringerBriefs in physics•Jan 1, 2020•15 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

Building intuition for quantum algorithms using the Aharonov–Bohm effect

Anna Liv Paludan Bjerregaard, K. Splittorff

Abstract Quantum computers operate in a manner so different from classical computers that our intuition for understanding the process of quantum computation is challenged. This not only makes it hard to develop new quantum algorithms, but also makes quantum computation a difficult subject for students. Here, we show that the time evolution of a particle on a ring with a coil through it performs the key quantum algorithm known as quantum phase estimation. The example uses the Aharonov–Bohm effect, and the aim is to help students build a physical intuition for quantum algorithms.

arXiv:2509.11893•European Journal of Physics•Jul 2, 2026•0 citations

When shall we have a quantum computer?

M. I. Dyakonov

•Jan 1, 2018•0 citations
In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A “trivial” or non-interactive PoQ simply assumes an (efficiently-verifiable) average-case hard problem for classical computers that is easy for quantum computers. However, there is much interest in “non-trivial” PoQs that actually rely on quantum hardness assumptions, instead of an assumed separation between quantum and classical computation for search problems, especially since these are often a starting point for more sophisticated protocols such as classical verification of quantum computation (CVQC). We show several lower-bounds for the hardness required to achieve non-trivial PoQ, specifically showing that they likely require cryptographic hardness, with different types of cryptographic hardness being required for different variations of non-trivial PoQ. In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ and its various extensions such as CVQC.
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.
Abstract Quantum computers operate in a manner so different from classical computers that our intuition for understanding the process of quantum computation is challenged. This not only makes it hard to develop new quantum algorithms, but also makes quantum computation a difficult subject for students. Here, we show that the time evolution of a particle on a ring with a coil through it performs the key quantum algorithm known as quantum phase estimation. The example uses the Aharonov–Bohm effect, and the aim is to help students build a physical intuition for quantum algorithms.