Quantum annealing-assisted framework for Search-LWE: a proof-of-concept study on a real quantum computer

The Learning With Errors (LWE) problem is fundamental in post-quantum cryptography, and its hardness ensures the security of many lattice-based cryptosystems. This paper proposes a quantum-classical framework for solving Search-LWE instances on real quantum annealing hardware using quantum tunneling to explore a restricted correction space around the Babai solution. First, the Search-LWE is formulated as a lattice decoding problem, and the restricted binary correction space around the Babai solution is encoded into an Ising Hamiltonian. Then, forward and reverse quantum annealing are implemented on the D-Wave Advantage2 to explore the correction space. In particular, reverse quantum annealing uses the Babai solution as the initial state for quantum annealing. The outputs of both quantum annealing schemes are refined by a classical local search to improve solution quality. Experimental results show that both quantum annealing approaches obtain lattice candidates with smaller residual error norms than the Babai solution for a consider-able number of tested instances. Simulated annealing further confirms the effectiveness of the Ising formulation. Moreover, our framework demonstrates successful secret recovery for Search-LWE instances with dimensions up to 15 on D-Wave Advantage2. These results provide a proof of concept on quantum hardware, but do not demonstrate a practical threat to cryptographically relevant LWE-based cryptosystems.

Authors

Institutions

Publication Details

Journal
Tsinghua Science & Technology
Published
2026-11-18
DOI
https://doi.org/10.26599/tst.2026.9010101
Primary Topic
Quantum Computing Algorithms and Architecture
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Quantum annealing-assisted framework for Search-LWE: a proof-of-concept study on a real quantum computer

Chunlei Hong, Shuaishuai Zhu, Han Yiliang, Yibo Li et al.
2 links
Tsinghua Science & Technology
Quantum Computing Algorithms and Architecture
article

Quantum annealing-assisted framework for Search-LWE: a proof-of-concept study on a real quantum computer

Chunlei Hong, Shuaishuai Zhu, Han Yiliang, Yibo Li, Shuaizhi Xiong, Zhi Pei, Yidan Chen, Chao Wang
article en

Abstract

The Learning With Errors (LWE) problem is fundamental in post-quantum cryptography, and its hardness ensures the security of many lattice-based cryptosystems. This paper proposes a quantum-classical framework for solving Search-LWE instances on real quantum annealing hardware using quantum tunneling to explore a restricted correction space around the Babai solution. First, the Search-LWE is formulated as a lattice decoding problem, and the restricted binary correction space around the Babai solution is encoded into an Ising Hamiltonian. Then, forward and reverse quantum annealing are implemented on the D-Wave Advantage2 to explore the correction space. In particular, reverse quantum annealing uses the Babai solution as the initial state for quantum annealing. The outputs of both quantum annealing schemes are refined by a classical local search to improve solution quality. Experimental results show that both quantum annealing approaches obtain lattice candidates with smaller residual error norms than the Babai solution for a consider-able number of tested instances. Simulated annealing further confirms the effectiveness of the Ising formulation. Moreover, our framework demonstrates successful secret recovery for Search-LWE instances with dimensions up to 15 on D-Wave Advantage2. These results provide a proof of concept on quantum hardware, but do not demonstrate a practical threat to cryptographically relevant LWE-based cryptosystems.

Tsinghua Science & Technology
Shanghai University (CN)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon