Row 4427

Row ID: 4427 | Dataset Entry | Axioma AXP Content Repository

Content Data

This page contains data entry 4427 from the Axioma AXP content repository. The structured data below represents the complete record for this entry.

We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev \[J.ACM 2009\], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all n-dimensional lattices within approximation factors of Ω\~(n\^4.5). Previously, no polynomial or even subexponential time quantum algorithms were known for solving GapSVP or SIVP for all lattices within any polynomial approximation factors.

To develop a quantum algorithm for solving LWE, we mainly introduce two new techniques. First, we introduce Gaussian functions with complex variances in the design of quantum algorithms. In particular, we exploit the feature of the Karst wave in the discrete Fourier transform of complex Gaussian functions. Second, we use windowed quantum Fourier transform with complex Gaussian windows, which allows us to combine the information from both time and frequency domains. Using those techniques, we first convert the LWE instance into quantum states with purely imaginary Gaussian amplitudes, then convert purely imaginary Gaussian states into classical linear equations over the LWE secret and error terms, and finally solve the linear system of equations using Gaussian elimination. This gives a polynomial time quantum algorithm for solving LWE.

Link [https://eprint.iacr.org/2024/555](https://eprint.iacr.org/2024/555)

Can this algorithm shake up PQC?

FieldValue
text We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev \[J.ACM 2009\], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all n-dimensional lattices within approximation factors of Ω\~(n\^4.5). Previously, no polynomial or even sub…
label r/quantumcomputing
dataType post
communityName r/QuantumComputing
datetime 2024-04-11
username_encoded Z0FBQUFBQm5LakwxSGVwNFZkX21VWV9Dc01iTlJ6UXZXb0MzbklsVHptYUk4cl9ObXpvWGZiZ0lZRC05a3RvZDZ0LUVmSTFDLWtPQi04UUFBWVU0YlhLN25Xa1pXTTBSMVE9PQ==
url_encoded Z0FBQUFBQm5Lak9GS19PbTcwV0RiTUJ0YjlCZWpYZFcxbm9fT3dTQ0dIS2toY20wemhxR1RHOEVyYzUzUnpJQXk5c1FTQ29zeHBBcnkxTmlScmVZbm1RNU9zZWJ1S25kQXc5XzlJRGVVTGhhcmVJc3Zwb3pwX2xoOV9QNmhHaVhrRGpkdmNBb2JOQ0lacjBpcHp4MmFoM192am1KTVN0RG5BZXBSM2M3bjM2WFltY1I4TWJMMjMtZTZrTVluTDRTeTY0N2FlODc2eXJKVVdjSlU4dmZnOHlEWVFKLWtqQTI0Zz09

Raw Record

{
  "text": "We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev \\[J.ACM 2009\\], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all n-dimensional lattices within approximation factors of Ω\\~(n\\^4.5). Previously, no polynomial or even subexponential time quantum algorithms were known for solving GapSVP or SIVP for all lattices within any polynomial approximation factors.  \n\nTo develop a quantum algorithm for solving LWE, we mainly introduce two new techniques. First, we introduce Gaussian functions with complex variances in the design of quantum algorithms. In particular, we exploit the feature of the Karst wave in the discrete Fourier transform of complex Gaussian functions. Second, we use windowed quantum Fourier transform with complex Gaussian windows, which allows us to combine the information from both time and frequency domains. Using those techniques, we first convert the LWE instance into quantum states with purely imaginary Gaussian amplitudes, then convert purely imaginary Gaussian states into classical linear equations over the LWE secret and error terms, and finally solve the linear system of equations using Gaussian elimination. This gives a polynomial time quantum algorithm for solving LWE.\n\nLink [https://eprint.iacr.org/2024/555](https://eprint.iacr.org/2024/555)\n\nCan this algorithm shake up PQC?",
  "label": "r/quantumcomputing",
  "dataType": "post",
  "communityName": "r/QuantumComputing",
  "datetime": "2024-04-11",
  "username_encoded": "Z0FBQUFBQm5LakwxSGVwNFZkX21VWV9Dc01iTlJ6UXZXb0MzbklsVHptYUk4cl9ObXpvWGZiZ0lZRC05a3RvZDZ0LUVmSTFDLWtPQi04UUFBWVU0YlhLN25Xa1pXTTBSMVE9PQ==",
  "url_encoded": "Z0FBQUFBQm5Lak9GS19PbTcwV0RiTUJ0YjlCZWpYZFcxbm9fT3dTQ0dIS2toY20wemhxR1RHOEVyYzUzUnpJQXk5c1FTQ29zeHBBcnkxTmlScmVZbm1RNU9zZWJ1S25kQXc5XzlJRGVVTGhhcmVJc3Zwb3pwX2xoOV9QNmhHaVhrRGpkdmNBb2JOQ0lacjBpcHp4MmFoM192am1KTVN0RG5BZXBSM2M3bjM2WFltY1I4TWJMMjMtZTZrTVluTDRTeTY0N2FlODc2eXJKVVdjSlU4dmZnOHlEWVFKLWtqQTI0Zz09"
}
Explore Dataset Explore Row

Entry Information