A relation between Krylov and Nielsen complexity

• URL: http://arxiv.org/abs/2311.18401v2
• Date: Thu, 18 Apr 2024 15:34:05 GMT
• Title: A relation between Krylov and Nielsen complexity
• Authors: Ben Craps, Oleg Evnin, Gabriele Pascuzzi,
• Abstract summary: Krylov complexity and Nielsen complexity are successful approaches to quantifying quantum evolution complexity. We show that there is a relation between the two quantities. Namely, the time average of Krylov complexity of state evolution can be expressed as a trace of a certain matrix.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Krylov complexity and Nielsen complexity are successful approaches to quantifying quantum evolution complexity that have been actively pursued without much contact between the two lines of research. The two quantities are motivated by quantum chaos and quantum computation, respectively, while the relevant mathematics is as different as matrix diagonalization algorithms and geodesic flows on curved manifolds. We demonstrate that, despite these differences, there is a relation between the two quantities. Namely, the time average of Krylov complexity of state evolution can be expressed as a trace of a certain matrix, which also controls an upper bound on Nielsen complexity with a specific custom-tailored penalty schedule adapted to the Krylov basis.

Related papers

• Spread complexity and quantum chaos for periodically driven spin chains [0.0]
  We study the dynamics of spread complexity for quantum maps using the Arnoldi iterative procedure. We find distinctive behaviour of the Arnoldi coefficients and spread complexity for regular vs. chaotic dynamics.
  arXiv  Detail & Related papers  (2024-05-25T11:17:43Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• 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)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Krylov Complexity of Fermionic and Bosonic Gaussian States [9.194828630186072]
  This paper focuses on emphKrylov complexity, a specialized form of quantum complexity. It offers an unambiguous and intrinsically meaningful assessment of the spread of a quantum state over all possible bases.
  arXiv  Detail & Related papers  (2023-09-19T07:32:04Z)
• Krylov complexity and chaos in quantum mechanics [0.0]
  We numerically evaluate Krylov complexity for operators and states. We find a clear correlation between variances of Lanczos coefficients and classical Lyapunov exponents. Our work provides a firm bridge between Krylov complexity and classical/quantum chaos.
  arXiv  Detail & Related papers  (2023-05-26T06:32:45Z)
• Krylov complexity in quantum field theory, and beyond [44.99833362998488]
  We study Krylov complexity in various models of quantum field theory. We find that the exponential growth of Krylov complexity satisfies the conjectural inequality, which generalizes the Maldacena-Shenker-Stanford bound on chaos.
  arXiv  Detail & Related papers  (2022-12-29T19:00:00Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• 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)
• 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)
• Aspects of The First Law of Complexity [0.0]
  We investigate the first law of complexity proposed in arXiv:1903.04511, i.e., the variation of complexity when the target state is perturbed. Based on Nielsen's geometric approach to quantum circuit complexity, we find the variation only depends on the end of the optimal circuit.
  arXiv  Detail & Related papers  (2020-02-13T21:15:57Z)

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.