Building Krylov complexity from circuit complexity
- URL: http://arxiv.org/abs/2303.07343v1
- Date: Mon, 13 Mar 2023 17:59:43 GMT
- Title: Building Krylov complexity from circuit complexity
- Authors: Chenwei Lv, Ren Zhang, Qi Zhou
- Abstract summary: 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.
- Score: 4.060731229044571
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Krylov complexity has emerged as a new probe of operator growth in a wide
range of non-equilibrium quantum dynamics. However, a fundamental issue remains
in such studies: the definition of the distance between basis states in Krylov
space is ambiguous. Here, we show that Krylov complexity can be rigorously
established from circuit complexity when dynamical symmetries exist. Whereas
circuit complexity characterizes the geodesic distance in a multi-dimensional
operator space, Krylov complexity measures the height of the final operator in
a particular direction. The geometric representation of circuit complexity thus
unambiguously designates the distance between basis states in Krylov space.
This geometric approach also applies to time-dependent Liouvillian
superoperators, where a single Krylov complexity is no longer sufficient.
Multiple Krylov complexity may be exploited jointly to fully describe operator
dynamics.
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) - 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) - Krylov complexity is not a measure of distance between states or operators [0.0]
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.
arXiv Detail & Related papers (2023-11-07T16:04:10Z) - Unitary Complexity and the Uhlmann Transformation Problem [41.67228730328207]
We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes.
We use this framework to study the complexity of transforming one entangled state into another via local operations.
Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
arXiv Detail & Related papers (2023-06-22T17:46:39Z) - 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) - Operator Complexity for Quantum Scalar Fields and Cosmological
Perturbations [0.0]
We study the complexity of the unitary evolution of quantum cosmological perturbations in de Sitter space.
The complexity of cosmological perturbations scales as the square root of the (exponentially) growing volume of de Sitter space.
arXiv Detail & Related papers (2021-10-15T20:37:36Z) - 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) - 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) - Relevant OTOC operators: footprints of the classical dynamics [68.8204255655161]
The OTOC-RE theorem relates the OTOCs summed over a complete base of operators to the second Renyi entropy.
We show that the sum over a small set of relevant operators, is enough in order to obtain a very good approximation for the entropy.
In turn, this provides with an alternative natural indicator of complexity, i.e. the scaling of the number of relevant operators with time.
arXiv Detail & Related papers (2020-07-31T19:23:26Z) - 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.