Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

Abstract

Shortest Vector Problem is believed to be hard both for classical and quantum computers. Two of the three NIST post-quantum cryptosystems standardised by NIST rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve SVP is crucial to establish confidence in them. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on NISQ devices have in solving SVP has been an active research area. The qubit-requirement for doing so has been analysed and it was demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian efficiently. Due to the heuristic nature of VQAs no analysis of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. Motivated by Boulebnane and Montanaro work on the k-SAT problem, we propose to use angle pretraining of the QAOA for SVP and we demonstrate that it 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 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. We observe time heuristic complexity $O(2^{0.695n})$, a bit worse than the fault-tolerant Grover approach of $O(2^{0.5n})$. However, both the number of qubits, and the depth of each quantum computation, are considerably better-Grover requires exponential depth, while each run of constant p fixed-angles QAOA requires polynomial depth. We also 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.

33pages, 5figures

References in corpus (22)

• A variational eigenvalue solver on a quantum processor
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Reachability Deficits in Quantum Approximate Optimization
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Parameter Concentration in Quantum Approximate Optimization
• Multistart Methods for Quantum Approximate Optimization
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Evaluating Quantum Approximate Optimization Algorithm: A Case Study
• Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
• Reinforcement Learning Assisted Recursive QAOA
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Not-so-adiabatic quantum computation for the shortest vector problem
• Variational quantum solutions to the Shortest Vector Problem
• Grover's oracle for the Shortest Vector Problem and its application in hybrid classical-quantum solvers
• Iterative Quantum Optimization with Adaptive Problem Hamiltonian
• Analysis of the shortest vector problems with the quantum annealing to search the excited states

Cited by in corpus (1)

• Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians