Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

• URL: http://arxiv.org/abs/2502.05284v1
• Date: Fri, 07 Feb 2025 19:42:35 GMT
• Title: Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• Authors: Miloš Prokop, Petros Wallden,
• Abstract summary: Shortest Vector Problem is believed to be hard for classical and quantum computers. We show that it is plausible to encode SVP on the ground state of a Hamiltonian efficiently. We propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits.
• Score: 0.0
• License:
• 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 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.

Related papers

• A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
  We propose a quantum-classical hybrid algorithm with Ising model (HAWI) to address the Learning-With-Errors (LWE) problem. We identify the low-energy levels of the Hamiltonian to extract the solution, making it suitable for implementation on current noisy intermediate-scale quantum (NISQ) devices. Our algorithm is iterations, and its time complexity depends on the specific quantum algorithm employed to find the Hamiltonian's low-energy levels.
  arXiv  Detail & Related papers  (2024-08-15T05:11:35Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• High-precision and low-depth eigenstate property estimation: theory and resource estimation [2.6811507121199325]
  Estimating the eigenstate properties of quantum many-body systems is a long-standing, challenging problem for both classical and quantum computing. Here, we present a full-stack design of a random sampling algorithm for estimating the eigenenergy and the observable expectations on the eigenstates.
  arXiv  Detail & Related papers  (2024-06-06T17:54:26Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  Variational quantum algorithms have become the de facto model for current quantum computations. One such problem is unstructured search which consists on finding a particular bit of string. We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
  arXiv  Detail & Related papers  (2024-03-22T18:00:03Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers [0.533024001730262]
  A classical vector $mathbfb$ is encoded in the amplitudes of a quantum state. An arbitrary state of $Q$ qubits generally requires approximately $2Q$ entangling gates. We present a deterministic (nonvariational) algorithm that allows one to flexibly reduce the quantum resources required for state preparation.
  arXiv  Detail & Related papers  (2021-10-26T07:37:54Z)
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup [9.820545418277305]
  We completely overhaul the QTDA algorithm to achieve an improved exponential speedup depth complexity of $O(n4/(epsilon2 delta)). We present a theoretical error analysis, and the circuit and computational time and depth complexities for Betti number estimation.
  arXiv  Detail & Related papers  (2021-08-05T18:56:17Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.