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
- Taming Quantum Time Complexity [50.10645865330582]
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) - Circuit Complexity through phase transitions: consequences in quantum
state preparation [0.0]
We analyze the circuit complexity for preparing ground states of quantum many-body systems.
In particular, how this complexity grows as the ground state approaches a quantum phase transition.
arXiv Detail & Related papers (2023-01-11T19:00:10Z) - 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) - 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) - 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)
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.