Bounds on quantum evolution complexity via lattice cryptography

• URL: http://arxiv.org/abs/2202.13924v3
• Date: Tue, 11 Oct 2022 15:28:03 GMT
• Title: Bounds on quantum evolution complexity via lattice cryptography
• Authors: Ben Craps, Marine De Clerck, Oleg Evnin, Philip Hacker, Maxim Pavlov
• Abstract summary: We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators. Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators. Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries. (An appropriate `complexity metric' must be used that takes into account the relative difficulty of performing `nonlocal' operations that act on many degrees of freedom at once.) While simply formulated and geometrically attractive, this notion of complexity is numerically intractable save for toy models with Hilbert spaces of very low dimensions. To bypass this difficulty, we trade the exact definition in terms of geodesics for an upper bound on complexity, obtained by minimizing the distance over an explicitly prescribed infinite set of curves, rather than over all possible curves. Identifying this upper bound turns out equivalent to the closest vector problem (CVP) previously studied in integer optimization theory, in particular, in relation to lattice-based cryptography. Effective approximate algorithms are hence provided by the existing mathematical considerations, and they can be utilized in our analysis of the upper bounds on quantum evolution complexity. The resulting algorithmically implemented complexity bound systematically assigns lower values to integrable than to chaotic systems, as we demonstrate by explicit numerical work for Hilbert spaces of dimensions up to ~10^4.

Related papers

• Upper bounds on quantum complexity of time-dependent oscillators [0.0]
  An explicit formula for an upper bound on the quantum complexity of a harmonic oscillator Hamiltonian with time-dependent frequency is derived. This result aligns with the gate complexity and earlier studies of de Sitter complexity. It provides a proof of concept for the application of Nielsen complexity in cosmology, together with a systematic setting in which higher-order terms can be included.
  arXiv  Detail & Related papers  (2024-07-01T18:00:03Z)
• The Complexity of Being Entangled [0.0]
  Nielsen's approach to quantum state complexity relates the minimal number of quantum gates required to prepare a state to the length of geodesics computed with a certain norm on the manifold of unitary transformations. For a bipartite system, we investigate binding complexity, which corresponds to norms in which gates acting on a single subsystem are free of cost.
  arXiv  Detail & Related papers  (2023-11-07T19:00:02Z)
• Geometric quantum complexity of bosonic oscillator systems [0.0]
  The length of the minimal geodesic in a geometric realization of a suitable operator space provides a measure of the quantum complexity of an operation. New insights about complexity can be found in a low-dimensional setting, with the potential of systematic extensions to higher dimensions as well as interactions.
  arXiv  Detail & Related papers  (2023-07-25T18:00:07Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Geometry of quantum complexity [0.0]
  Computational complexity is a new quantum information concept that may play an important role in holography. We consider quantum computational complexity for $n$ qubits using Nielsen's geometrical approach.
  arXiv  Detail & Related papers  (2020-11-15T18:41:19Z)
• Operator complexity: a journey to the edge of Krylov space [0.0]
  Krylov complexity, or K-complexity', quantifies this growth with respect to a special basis. We study the evolution of K-complexity in finite-entropy systems for time scales greater than the scrambling time.
  arXiv  Detail & Related papers  (2020-09-03T18:10:20Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

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.