Quantum-Classical Hybrid Algorithm for Solving the Learning-With-Errors Problem on NISQ Devices
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918264706170880 |
|---|---|
| author | Zheng, Muxi Zeng, Jinfeng Yang, Wentao Chang, Pei-Jie Lu, Quanfeng Yan, Bao Zhang, Haoran Wang, Min Wei, Shijie Long, Gui-Lu |
| author_facet | Zheng, Muxi Zeng, Jinfeng Yang, Wentao Chang, Pei-Jie Lu, Quanfeng Yan, Bao Zhang, Haoran Wang, Min Wei, Shijie Long, Gui-Lu |
| contents | The Learning-With-Errors (LWE) problem is a fundamental computational challenge with implications for post-quantum cryptography and computational learning theory. Here we propose a quantum-classical hybrid algorithm with Ising model to address LWE, transforming it into the Shortest Vector Problem and using variable qubits to encode lattice vectors into an Ising Hamiltonian. By identifying low-energy Hamiltonian levels, the solution is extracted, making the method suitable for noisy intermediate-scale quantum devices. The required number of qubits is less than $m(m+1)$, where $m$ is the number of samples. Our heuristic algorithm's time complexity depends on the specific quantum eigensolver used to find low-energy levels, and the performance when using the Quantum Approximate Optimization Algorithm is investigated. We validate the algorithm by solving a $2$-dimensional LWE problem on a $5$-qubit quantum device, demonstrating its potential for solving meaningful LWE instances on near-term quantum devices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07936 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum-Classical Hybrid Algorithm for Solving the Learning-With-Errors Problem on NISQ Devices Zheng, Muxi Zeng, Jinfeng Yang, Wentao Chang, Pei-Jie Lu, Quanfeng Yan, Bao Zhang, Haoran Wang, Min Wei, Shijie Long, Gui-Lu Quantum Physics Mathematical Physics The Learning-With-Errors (LWE) problem is a fundamental computational challenge with implications for post-quantum cryptography and computational learning theory. Here we propose a quantum-classical hybrid algorithm with Ising model to address LWE, transforming it into the Shortest Vector Problem and using variable qubits to encode lattice vectors into an Ising Hamiltonian. By identifying low-energy Hamiltonian levels, the solution is extracted, making the method suitable for noisy intermediate-scale quantum devices. The required number of qubits is less than $m(m+1)$, where $m$ is the number of samples. Our heuristic algorithm's time complexity depends on the specific quantum eigensolver used to find low-energy levels, and the performance when using the Quantum Approximate Optimization Algorithm is investigated. We validate the algorithm by solving a $2$-dimensional LWE problem on a $5$-qubit quantum device, demonstrating its potential for solving meaningful LWE instances on near-term quantum devices. |
| title | Quantum-Classical Hybrid Algorithm for Solving the Learning-With-Errors Problem on NISQ Devices |
| topic | Quantum Physics Mathematical Physics |
| url | https://arxiv.org/abs/2408.07936 |