Krylov complexity is not a measure of distance between states or operators

• URL: http://arxiv.org/abs/2311.04093v2
• Date: Tue, 19 Mar 2024 14:50:33 GMT
• Title: Krylov complexity is not a measure of distance between states or operators
• Authors: Sergio E. Aguilar-Gutierrez, Andrew Rolph,
• Abstract summary: We show that Krylov complexities between three states fail to satisfy the triangle inequality. There is no possible metric for which Krylov complexity is the length of the shortest path to the target state or operator.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We ask whether Krylov complexity is mutually compatible with the circuit and Nielsen definitions of complexity. We show that the Krylov complexities between three states fail to satisfy the triangle inequality and so cannot be a measure of distance: there is no possible metric for which Krylov complexity is the length of the shortest path to the target state or operator. We show this explicitly in the simplest example, a single qubit, and in general.

Related papers

• The complexity of entanglement embezzlement [0.0]
  We study the circuit complexity of embezzlement using sequences of states that enable arbitrary precision for the process. Our results imply that circuit complexity acts as a physical obstruction to perfect embezzlement.
  arXiv  Detail & Related papers  (2024-10-24T18:00:33Z)
• 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)
• Can Large Language Models Understand Real-World Complex Instructions? [54.86632921036983]
  Large language models (LLMs) can understand human instructions, but struggle with complex instructions. Existing benchmarks are insufficient to assess LLMs' ability to understand complex instructions. We propose CELLO, a benchmark for evaluating LLMs' ability to follow complex instructions systematically.
  arXiv  Detail & Related papers  (2023-09-17T04:18:39Z)
• Unextendibility, uncompletability, and many-copy indistinguishable ensembles [77.34726150561087]
  We study unextendibility, uncompletability and analyze their connections to many-copy indistinguishable ensembles. We report a class of multipartite many-copy indistinguishable ensembles for which local indistinguishability property increases with decreasing mixedness.
  arXiv  Detail & Related papers  (2023-03-30T16:16:41Z)
• Building Krylov complexity from circuit complexity [4.060731229044571]
  We show that Krylov complexity can be rigorously established from circuit complexity when dynamical symmetries exist. Multiple Krylov complexity may be exploited jointly to fully describe operator dynamics.
  arXiv  Detail & Related papers  (2023-03-13T17:59:43Z)
• A universal approach to Krylov State and Operator complexities [0.0]
  In our formalism, the Krylov complexity is defined in terms of the density matrix of the associated state. This unified definition of complexity enables us to extend the notion of Krylov complexity to subregion or mixed state complexities.
  arXiv  Detail & Related papers  (2022-12-20T19:00:12Z)
• Bounds on quantum evolution complexity via lattice cryptography [0.0]
  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.
  arXiv  Detail & Related papers  (2022-02-28T16:20:10Z)
• Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
  We formulate novel fast NonLocal blocks, capable of reducing complexity from quadratic to linear with no loss in performance. The proposed method, which we dub as "Poly-NL", is competitive with state-of-the-art performance across image recognition, instance segmentation, and face detection tasks.
  arXiv  Detail & Related papers  (2021-07-06T19:51:37Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  We study oracle complexity of gradient based methods for approximation problems. We focus on instance-dependent complexity instead of worst case complexity. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation.
  arXiv  Detail & Related papers  (2020-06-08T09:25:47Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)

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.