Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2402.13895 · IEEE Transactions on Quantum Engineering

Grover's Oracle for the Shortest Vector Problem and Its Application in Hybrid Classical–Quantum Solvers

Miloš Prokop, Petros Wallden, David Joseph

Published Nov 18, 2024• 7 citations
arXivHTMLPDF

Abstract

Finding the shortest vector in a lattice is a problem that is believed to be hard both for classical and quantum computers. Many major postquantum secure cryptosystems base their security on the hardness of the shortest vector problem (SVP) (Moody, 2023). Finding the best classical, quantum, or hybrid classical–quantum algorithms for the SVP is necessary to select cryptosystem parameters that offer a sufficient level of security. Grover's search quantum algorithm provides a generic quadratic speedup, given access to an oracle implementing some function, which describes when a solution is found. In this article, we provide concrete implementation of such an oracle for the SVP. We define the circuit and evaluate costs in terms of the number of qubits, the number of gates, depth, and T-quantum cost. We then analyze how to combine Grover's quantum search for small SVP instances with state-of-the-art classical solvers that use well-known algorithms, such as the block Korkine Zolotorev (Schnorr and Euchner, 1994), where the former is used as a subroutine. This could enable solving larger instances of SVP with higher probability than classical state-of-the-art records, but still very far from posing any threat to cryptosystems being considered for standardization. Depending on the technology available, there is a spectrum of tradeoffs in creating this combination.

DOI
10.1109/tqe.2024.3501683

Related papers

Estimates of Implementation Complexity for Quantum Cryptanalysis of Post-Quantum Lattice-Based Cryptosystems

Alexander Olegovich Bakharev

Abstract Due to the development of quantum computing, there is a need for the development and analysis of cryptosystems resistant to attacks using a quantum computer (post-quantum cryptography algorithms). The security of many well-known post-quantum cryptosystems based on lattice theory depends on the complexity of solving the shortest vector problem (SVP). In this paper, a model of quantum oracle developed from Grover’s algorithm is described to implement a hybrid quantum–classical algorithm based on GaussSieve. This algorithm can be used for attacks on cryptosystems whose security depends on solving the SVP. Upper bounds for the number of qubits and the depth of the circuit were obtained for two implementations of the proposed quantum oracle model: minimizing the number of qubits and minimizing the circuit depth. The complexity of implementing the proposed quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed.

Journal of Applied and Industrial Mathematics•Sep 1, 2023•1 citation

Upper bounds of complexity of quantum oracle for problem of finding shortest vector on integer lattice

Alexander Olegovich Bakharev

Due to the development of quantum computing, there is a need for development and analysis of cryptosystems resistant to attacks with using a quantum computer - post-quantum algorithms cryptography. The strength of many well-known post-quantum cryptosystems, based on the theory of lattices, is based on the complexity of solving the problem finding the shortest vector in the lattice (SVP). For the previously proposed models of the quantum oracle used in the hybrid quantum-classical algorithm for solving the SVP problem, new refined estimates of implementation complexity. Designed and analyzed a new quantum oracle model that uses classical memory to storing a list of vectors.

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"•Jan 1, 2022•0 citations

Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

Miloš Prokop, Petros Wallden

Finding the shortest non-zero vector on a lattice is a fundamental problem in lattices that is believed to be hard both for classical and quantum computers. Two of the three standardised by NIST post-quantum cryptosystems rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve the Shortest Vector Problem (SVP) is crucial to establish confidence in those new standards. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on Noisy Intermediate Scale Quantum (NISQ) devices have in solving SVP has been an active area of research. The qubit-requirement for doing so has been analysed and demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian in an efficient way. Due to the heuristic nature of VQAs no analysis of the performance and specifically of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. In this paper, motivated by Boulebnane and Montanaro [1] work on the k-SAT problem, we propose to use angle pretraining of the Quantum Approximate Optimisation Algorithm (QAOA) for SVP and we demonstrate that QAOA with fixed angles performs well on much larger instances than those used in training. Avoiding the limitations that arise due to the use of optimiser, we are able to extrapolate the observed performance and we observe the probability of success scaling as$2^{-0.695n}$with$n$being dimensionality of the search space for a depth$p=3$pre-trained QAOA algorithm. By repeating the algorithm, we get heuristic time complexity$O(2^{0.695n})$to solve the problem with high probability, a bit worse than the fault-tolerant Grover approach of$O(2^{0.5n})$. On the other hand, both the number of qubits, and most importantly the depth of each quantum computation, are considerably better in our approach – Grover requires exponential depth, while each run of constant$p$fixed-angles QAOA requires polynomial depth. Further, we analyse the performance of QAOA in solving approximate-SVP, a version of the problem that one seeks a multiplicative approximation to the shortest vector. As a side result, we propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits. This improves upon the previous works as it results in more space efficient encoding of SVP on NISQ architectures without ignoring the zero vector problem.

arXiv:2502.05284•IEEE Transactions on Quantum Engineering•Jan 1, 2025•2 citations

Finding dense sublattices as low energy states of a Hamiltonian

Júlia Barberà-Rodríguez, Nicolas Gama, Anand Kumar Narayanan +1 more

Lattice-based cryptography has emerged as one of the most prominent candidates for postquantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest nonzero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the K -Densest Sublattice Problem ( K -DSP): to find the densest K -dimensional sublattice of a given lattice. We formulate K -DSP as finding the first excited state of a Z -basis Hamiltonian, making K -DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and variational quantum algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that O ( K N 2 ) qubits suffice for solving K -DSP for N -dimensional input lattices. We empirically demonstrate the performance of a quantum approximate optimization algorithm K -DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of K -DSP in relation to the SVP, to see if there is a reason to build postquantum cryptography on K -DSP. We devise a quantum algorithm that solves K -DSP with runtime exponent ( 5 K N log 2 N ) / 2 . Therefore, for fixed K , K -DSP is no more than polynomially harder than the SVP. The central insight we use is similar in spirit to those underlying the best-known classical K -DSP algorithm due to Dadush and Micciancio. Whether the exponential dependence on K can be lowered remains an open question. Published by the American Physical Society 2024

arXiv:2309.16256•Physical Review Research•Dec 16, 2024•1 citation

A New Quantum Oracle Model for a Hybrid Quantum-Classical Attack on Post-Quantum Lattice-Based Cryptosystems

Alexander Olegovich Bakharev

Abstract Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetric cryptography currently in use. Most attacks on these cryptosystems can be reduced to the shortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oracle model from Grover’s algorithm to implement a hybrid quantum-classical algorithm based on the GaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle is proposed and analyzed. Two implementations of the new quantum oracle model are proposed and estimated. The complexity of implementing the new quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed. Comparison of obtained results for new and existing models of quantum oracle is given.

Journal of Applied and Industrial Mathematics•Jun 1, 2024•1 citation

Concrete Quantum Sieve for Shortest Vector Problem With Application to Lattice-Based Cryptography

Hyunji Kim, Kyungbae Jang, Anubhab Baksi +4 more

This paper presents a concrete quantum implementation and resource estimates for the Grover-assisted Nguyen–Vidick (NV) sieve oracle for solving the Shortest Vector Problem (SVP) in lattice-based cryptography. We focus on optimizing the product of the qubit count and circuit depth for a Grover-assisted quantum sieve by combining an in-place carry-lookahead adder and a quantum carry-save adder. Our oracle reduces circuit depth and achieves an improvement of 20%–77% in the qubit count-T-depth product compared to Cho et al. (CHES’25). Using selected core-SVP dimensions associated with the target lattice-based schemes, including National Institute of Standards and Technology (NIST) standards and Korean Post-Quantum Cryptography (KpqC) algorithms, we estimate quantum resources under the adopted heuristic NV-sieve iteration model. The resulting core-SVP costs cover both the plain NV sieve and the spherical locality-sensitive filtering (LSF) variant, and incorporate memory-access costs from read-only quantum lookup circuits. In accordance with the NIST security criteria, our implementation for the core-SVP yields a circuit depth exceeding the MAXDEPTH upper bound of 296, and its total gate count-depth metric significantly exceeds the NIST post-quantum security thresholds corresponding to all evaluated instances. We further estimate surface-code-based fault-tolerant resources under multiple physical error rates and cycle times. As one of our estimates, solving the core-SVP for ML-KEM-512 (NIST post-quantum security level 1) with LSF and low-depth quantum lookup requires approximately 2113 years using 246 physical qubits under p = 10−4 and a 200 ns cycle time.

IEEE Access•Jan 1, 2026•0 citations
Finding the shortest vector in a lattice is a problem that is believed to be hard both for classical and quantum computers. Many major postquantum secure cryptosystems base their security on the hardness of the shortest vector problem (SVP) (Moody, 2023). Finding the best classical, quantum, or hybrid classical–quantum algorithms for the SVP is necessary to select cryptosystem parameters that offer a sufficient level of security. Grover's search quantum algorithm provides a generic quadratic speedup, given access to an oracle implementing some function, which describes when a solution is found. In this article, we provide concrete implementation of such an oracle for the SVP. We define the circuit and evaluate costs in terms of the number of qubits, the number of gates, depth, and T-quantum cost. We then analyze how to combine Grover's quantum search for small SVP instances with state-of-the-art classical solvers that use well-known algorithms, such as the block Korkine Zolotorev (Schnorr and Euchner, 1994), where the former is used as a subroutine. This could enable solving larger instances of SVP with higher probability than classical state-of-the-art records, but still very far from posing any threat to cryptosystems being considered for standardization. Depending on the technology available, there is a spectrum of tradeoffs in creating this combination.
Abstract Due to the development of quantum computing, there is a need for the development and analysis of cryptosystems resistant to attacks using a quantum computer (post-quantum cryptography algorithms). The security of many well-known post-quantum cryptosystems based on lattice theory depends on the complexity of solving the shortest vector problem (SVP). In this paper, a model of quantum oracle developed from Grover’s algorithm is described to implement a hybrid quantum–classical algorithm based on GaussSieve. This algorithm can be used for attacks on cryptosystems whose security depends on solving the SVP. Upper bounds for the number of qubits and the depth of the circuit were obtained for two implementations of the proposed quantum oracle model: minimizing the number of qubits and minimizing the circuit depth. The complexity of implementing the proposed quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed.
Due to the development of quantum computing, there is a need for development and analysis of cryptosystems resistant to attacks with using a quantum computer - post-quantum algorithms cryptography. The strength of many well-known post-quantum cryptosystems, based on the theory of lattices, is based on the complexity of solving the problem finding the shortest vector in the lattice (SVP). For the previously proposed models of the quantum oracle used in the hybrid quantum-classical algorithm for solving the SVP problem, new refined estimates of implementation complexity. Designed and analyzed a new quantum oracle model that uses classical memory to storing a list of vectors.
Finding the shortest non-zero vector on a lattice is a fundamental problem in lattices that is believed to be hard both for classical and quantum computers. Two of the three standardised by NIST post-quantum cryptosystems rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve the Shortest Vector Problem (SVP) is crucial to establish confidence in those new standards. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on Noisy Intermediate Scale Quantum (NISQ) devices have in solving SVP has been an active area of research. The qubit-requirement for doing so has been analysed and demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian in an efficient way. Due to the heuristic nature of VQAs no analysis of the performance and specifically of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. In this paper, motivated by Boulebnane and Montanaro [1] work on the k-SAT problem, we propose to use angle pretraining of the Quantum Approximate Optimisation Algorithm (QAOA) for SVP and we demonstrate that QAOA with fixed angles performs well on much larger instances than those used in training. Avoiding the limitations that arise due to the use of optimiser, we are able to extrapolate the observed performance and we observe the probability of success scaling as2−0.695n2^{-0.695n}2−0.695nwithnnnbeing dimensionality of the search space for a depthp=3p=3p=3pre-trained QAOA algorithm. By repeating the algorithm, we get heuristic time complexityO(20.695n)O(2^{0.695n})O(20.695n)to solve the problem with high probability, a bit worse than the fault-tolerant Grover approach ofO(20.5n)O(2^{0.5n})O(20.5n). On the other hand, both the number of qubits, and most importantly the depth of each quantum computation, are considerably better in our approach – Grover requires exponential depth, while each run of constantpppfixed-angles QAOA requires polynomial depth. Further, we analyse the performance of QAOA in solving approximate-SVP, a version of the problem that one seeks a multiplicative approximation to the shortest vector. As a side result, we propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits. This improves upon the previous works as it results in more space efficient encoding of SVP on NISQ architectures without ignoring the zero vector problem.
Lattice-based cryptography has emerged as one of the most prominent candidates for postquantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest nonzero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the K -Densest Sublattice Problem ( K -DSP): to find the densest K -dimensional sublattice of a given lattice. We formulate K -DSP as finding the first excited state of a Z -basis Hamiltonian, making K -DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and variational quantum algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that O ( K N 2 ) qubits suffice for solving K -DSP for N -dimensional input lattices. We empirically demonstrate the performance of a quantum approximate optimization algorithm K -DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of K -DSP in relation to the SVP, to see if there is a reason to build postquantum cryptography on K -DSP. We devise a quantum algorithm that solves K -DSP with runtime exponent ( 5 K N log 2 N ) / 2 . Therefore, for fixed K , K -DSP is no more than polynomially harder than the SVP. The central insight we use is similar in spirit to those underlying the best-known classical K -DSP algorithm due to Dadush and Micciancio. Whether the exponential dependence on K can be lowered remains an open question. Published by the American Physical Society 2024
Abstract Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetric cryptography currently in use. Most attacks on these cryptosystems can be reduced to the shortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oracle model from Grover’s algorithm to implement a hybrid quantum-classical algorithm based on the GaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle is proposed and analyzed. Two implementations of the new quantum oracle model are proposed and estimated. The complexity of implementing the new quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed. Comparison of obtained results for new and existing models of quantum oracle is given.
This paper presents a concrete quantum implementation and resource estimates for the Grover-assisted Nguyen–Vidick (NV) sieve oracle for solving the Shortest Vector Problem (SVP) in lattice-based cryptography. We focus on optimizing the product of the qubit count and circuit depth for a Grover-assisted quantum sieve by combining an in-place carry-lookahead adder and a quantum carry-save adder. Our oracle reduces circuit depth and achieves an improvement of 20%–77% in the qubit count-T-depth product compared to Cho et al. (CHES’25). Using selected core-SVP dimensions associated with the target lattice-based schemes, including National Institute of Standards and Technology (NIST) standards and Korean Post-Quantum Cryptography (KpqC) algorithms, we estimate quantum resources under the adopted heuristic NV-sieve iteration model. The resulting core-SVP costs cover both the plain NV sieve and the spherical locality-sensitive filtering (LSF) variant, and incorporate memory-access costs from read-only quantum lookup circuits. In accordance with the NIST security criteria, our implementation for the core-SVP yields a circuit depth exceeding the MAXDEPTH upper bound of 296, and its total gate count-depth metric significantly exceeds the NIST post-quantum security thresholds corresponding to all evaluated instances. We further estimate surface-code-based fault-tolerant resources under multiple physical error rates and cycle times. As one of our estimates, solving the core-SVP for ML-KEM-512 (NIST post-quantum security level 1) with LSF and low-depth quantum lookup requires approximately 2113 years using 246 physical qubits under p = 10−4 and a 200 ns cycle time.