It's not particularly related. We have efficient quantum algorithms for RSA and discrete logarithms. Both are solved by viewing them as instances of the "hidden subgroup problem" over an abelian group.
Some well-known other problems are also HSP instances over non-abelian groups, for example
1. the learning with errors assumption (the main PQ thing people like) is a HSP instance over the dihedral group, and
2. graph-isomorphism is a HSP instance over the symmetric group.
LWE appears to be quite hard classically (SOTA attacks are 2^{~0.3n} time and exponential memory). Graph isomorphism is a famously easy problem outside of P, namely it is in quasi-polynomial time. So the fact that both are not in BQP doesn't say much about their relative classical difficulty.
This is precisely the uncertainty that the commenter above was referring to when they mentioned complexity classes like BQP. We don't necessarily know the precise relationship between quantum complexity classes and their classical counterparts.
There is more certainty about the resilience of lattice cryptography to classical attack than there was about Curve25519's resilience when it was introduced. Lattice schemes weren't invented as PQC schemes; they were invented as faster classical schemes. In the 1990s, there was a live debate about whether lattices might be the successor to RSA, not curves.
With the caveat (for other commenters) that "lattices" means several things that were not viewed with a unified lens in the 90s and 2000s, the main lattice scheme of interest now (LWE) actually was introduced in a quite literal sense as a PQC scheme.
In the early 2000s, Oded Regev was looking into quantum computing algorithms for various worst-case lattice problems. He was able to create an efficient quantum algorithm for a particular one (SIVP_\gamma), if he could only obtain an efficient quantum algorithm for a certain novel/simple problem (the learning with errors problem). He was unable to do this, so instead framed his result as a reduction from SIVP_\gamma to LWE, and additionally showed how one can build cryptography from LWE. This is essentially the contents of his 2005 LWE paper, for which he later got the Godel prize.
So in a quite literal sense, LWE is the byproduct of a failed search for a quantum algorithm for SIVP_\gamma, and was therefore "post-quantum from the start". Regev mentions this as his initial motivation for looking into LWE on page 4 of his LWE survey
It's not particularly related. We have efficient quantum algorithms for RSA and discrete logarithms. Both are solved by viewing them as instances of the "hidden subgroup problem" over an abelian group.
Some well-known other problems are also HSP instances over non-abelian groups, for example
1. the learning with errors assumption (the main PQ thing people like) is a HSP instance over the dihedral group, and
2. graph-isomorphism is a HSP instance over the symmetric group.
LWE appears to be quite hard classically (SOTA attacks are 2^{~0.3n} time and exponential memory). Graph isomorphism is a famously easy problem outside of P, namely it is in quasi-polynomial time. So the fact that both are not in BQP doesn't say much about their relative classical difficulty.
This is precisely the uncertainty that the commenter above was referring to when they mentioned complexity classes like BQP. We don't necessarily know the precise relationship between quantum complexity classes and their classical counterparts.
There is more certainty about the resilience of lattice cryptography to classical attack than there was about Curve25519's resilience when it was introduced. Lattice schemes weren't invented as PQC schemes; they were invented as faster classical schemes. In the 1990s, there was a live debate about whether lattices might be the successor to RSA, not curves.
With the caveat (for other commenters) that "lattices" means several things that were not viewed with a unified lens in the 90s and 2000s, the main lattice scheme of interest now (LWE) actually was introduced in a quite literal sense as a PQC scheme.
In the early 2000s, Oded Regev was looking into quantum computing algorithms for various worst-case lattice problems. He was able to create an efficient quantum algorithm for a particular one (SIVP_\gamma), if he could only obtain an efficient quantum algorithm for a certain novel/simple problem (the learning with errors problem). He was unable to do this, so instead framed his result as a reduction from SIVP_\gamma to LWE, and additionally showed how one can build cryptography from LWE. This is essentially the contents of his 2005 LWE paper, for which he later got the Godel prize.
So in a quite literal sense, LWE is the byproduct of a failed search for a quantum algorithm for SIVP_\gamma, and was therefore "post-quantum from the start". Regev mentions this as his initial motivation for looking into LWE on page 4 of his LWE survey
https://cims.nyu.edu/~regev/papers/lwesurvey.pdf
The international standardization effort that led to ML-KEM and ML-DSA focused both on classical attacks (regular computers) and quantum attacks.
There were 5 levels being considered for each submission.
Level 1 - at least as difficult to attack as AES-128 (block cipher)
Level 2 - at least as difficult to attack as SHA-256 (hash function)
Level 3 - at least as difficult to attack as AES-192 (block cipher)
Level 4 - at least as difficult to attack as SHA-384 (hash function)
Level 5 - at least as difficult to attack as AES-256 (block cipher)
The security of attacking an N-bit block cipher is morally congruent to a birthday collision against a {2N}-bit hash function. With some caveats: https://soatok.blog/2024/07/01/blowing-out-the-candles-on-th...
ML-DSA-44 (smallest parameter set) targets Level 2 for signatures.
ML-KEM-768 targets Level 3 for KEMs.