@article{Joseph:2021:10.1103/PhysRevA.103.032433,
author = {Joseph, D and Callison, A and Ling, C and Mintert, F},
doi = {10.1103/PhysRevA.103.032433},
journal = {Physical Review A: Atomic, Molecular and Optical Physics},
pages = {1--12},
title = {Two quantum Ising algorithms for the shortest-vector problem},
url = {http://dx.doi.org/10.1103/PhysRevA.103.032433},
volume = {103},
year = {2021}
}

Download

TY  - JOUR
AB  - Quantum computers are expected to break today's public key cryptography within a few decades. New cryptosystems are being designed and standardized for the postquantum era, and a significant proportion of these rely on the hardness of problems like the shortest-vector problem to a quantum adversary. In this paper we describe two variants of a quantum Ising algorithm to solve this problem. One variant is spatially efficient, requiring only O(Nlog2N) qubits, where N is the lattice dimension, while the other variant is more robust to noise. Analysis of the algorithms' performance on a quantum annealer and in numerical simulations shows that the more qubit-efficient variant will outperform in the long run, while the other variant is more suitable for near-term implementation.
AU  - Joseph,D
AU  - Callison,A
AU  - Ling,C
AU  - Mintert,F
DO  - 10.1103/PhysRevA.103.032433
EP  - 12
PY  - 2021///
SN  - 1050-2947
SP  - 1
TI  - Two quantum Ising algorithms for the shortest-vector problem
T2  - Physical Review A: Atomic, Molecular and Optical Physics
UR  - http://dx.doi.org/10.1103/PhysRevA.103.032433
UR  - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000646066000003&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
UR  - https://journals.aps.org/pra/abstract/10.1103/PhysRevA.103.032433
UR  - http://hdl.handle.net/10044/1/91535
VL  - 103
ER  - 

Download