An Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors

• URL: http://arxiv.org/abs/2310.03735v2
• Date: Tue, 7 Nov 2023 15:31:56 GMT
• Title: An Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors
• Authors: Yi-Kai Liu
• Abstract summary: We show the infeasibility of one approach to constructing quantum algorithms for solving lattice problems. We show that, for any choice of the Gaussian-like wave function, the error in this step will be above the threshold required to solve BDD and approximate-SVP.
• Score: 0.6889425872704066
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The curvelet transform is a special type of wavelet transform, which is useful for estimating the locations and orientations of waves propagating in Euclidean space. We prove an uncertainty principle that lower-bounds the variance of these estimates, for radial wave functions in n dimensions. As an application of this uncertainty principle, we show the infeasibility of one approach to constructing quantum algorithms for solving lattice problems, such as the approximate shortest vector problem (approximate-SVP), and bounded distance decoding (BDD). This gives insight into the computational intractability of approximate-SVP, which plays an important role in algorithms for integer programming, and in post-quantum cryptosystems. In this approach to solving lattice problems, one prepares quantum superpositions of Gaussian-like wave functions centered at lattice points. A key step in this procedure requires finding the center of each Gaussian-like wave function, using the quantum curvelet transform. We show that, for any choice of the Gaussian-like wave function, the error in this step will be above the threshold required to solve BDD and approximate-SVP.

Related papers

• Efficient Computation of the Quantum Rate-Distortion Function [6.281229317487581]
  We show how symmetry reduction can significantly simplify common instances of the entanglement-assisted quantum rate-distortion problems. We propose an inexact variant of the mirror descent algorithm to compute the quantum rate-distortion function with provable sublinear convergence rates.
  arXiv  Detail & Related papers  (2023-09-28T00:46:53Z)
• Randomized semi-quantum matrix processing [0.0]
  We present a hybrid quantum-classical framework for simulating generic matrix functions. The method is based on randomization over the Chebyshev approximation of the target function. We prove advantages on average depths, including quadratic speed-ups on costly parameters.
  arXiv  Detail & Related papers  (2023-07-21T18:00:28Z)
• GRAPE optimization for open quantum systems with time-dependent decoherence rates driven by coherent and incoherent controls [77.34726150561087]
  The GRadient Ascent Pulse Engineering (GRAPE) method is widely used for optimization in quantum control. We adopt GRAPE method for optimizing objective functionals for open quantum systems driven by both coherent and incoherent controls. The efficiency of the algorithm is demonstrated through numerical simulations for the state-to-state transition problem.
  arXiv  Detail & Related papers  (2023-07-17T13:37:18Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• Efficient Light Propagation Algorithm using Quantum Computers [0.3124884279860061]
  One of the cornerstones in modern optics is the beam propagation algorithm. We show that the propagation can be performed as a quantum computation with $mathcalO(logN)$ single-controlled phase gates. We highlight the importance of the selection of suitable observables to retain the quantum advantage.
  arXiv  Detail & Related papers  (2023-03-13T11:47:09Z)
• Quantum Gate Generation in Two-Level Open Quantum Systems by Coherent and Incoherent Photons Found with Gradient Search [77.34726150561087]
  We consider an environment formed by incoherent photons as a resource for controlling open quantum systems via an incoherent control. We exploit a coherent control in the Hamiltonian and an incoherent control in the dissipator which induces the time-dependent decoherence rates.
  arXiv  Detail & Related papers  (2023-02-28T07:36:02Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Variational waveguide QED simulators [58.720142291102135]
  Waveguide QED simulators are made by quantum emitters interacting with one-dimensional photonic band-gap materials. Here, we demonstrate how these interactions can be a resource to develop more efficient variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-02-03T18:55:08Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• Bosonic field digitization for quantum computers [62.997667081978825]
  We address the representation of lattice bosonic fields in a discretized field amplitude basis. We develop methods to predict error scaling and present efficient qubit implementation strategies.
  arXiv  Detail & Related papers  (2021-08-24T15:30:04Z)
• Calculating the distance from an electronic wave function to the manifold of Slater determinants through the geometry of Grassmannians [0.0]
  We propose an algorithm that converges to a Slater determinant that is critical point of the overlap function with a correlated wave function. This algorithm can be applied to quantify the entanglement or correlation of a wave function.
  arXiv  Detail & Related papers  (2020-12-09T19:46:47Z)

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.