Quantum Kolmogorov complexity and quantum correlations in
deterministic-control quantum Turing machines
- URL: http://arxiv.org/abs/2305.14252v3
- Date: Mon, 15 Jan 2024 16:57:59 GMT
- Title: Quantum Kolmogorov complexity and quantum correlations in
deterministic-control quantum Turing machines
- Authors: Mariano Lemus, Ricardo Faleiro, Paulo Mateus, Nikola Paunkovi\'c,
Andr\'e Souto
- Abstract summary: This work presents a study of Kolmogorov complexity for general quantum states from the perspective of deterministic-control quantum Turing Machines (dcq-TM)
We extend the dcq-TM model to incorporate mixed state inputs and outputs, and define dcq-computable states as those that can be approximated by a dcq-TM.
- Score: 0.9374652839580183
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work presents a study of Kolmogorov complexity for general quantum
states from the perspective of deterministic-control quantum Turing Machines
(dcq-TM). We extend the dcq-TM model to incorporate mixed state inputs and
outputs, and define dcq-computable states as those that can be approximated by
a dcq-TM. Moreover, we introduce (conditional) Kolmogorov complexity of quantum
states and use it to study three particular aspects of the algorithmic
information contained in a quantum state: a comparison of the information in a
quantum state with that of its classical representation as an array of real
numbers, an exploration of the limits of quantum state copying in the context
of algorithmic complexity, and study of the complexity of correlations in
quantum systems, resulting in a correlation-aware definition for algorithmic
mutual information that satisfies symmetry of information property.
Related papers
- Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process.
We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable.
Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs.
We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
arXiv Detail & Related papers (2024-05-12T09:05:13Z) - An operational definition of quantum information scrambling [0.0]
Quantum information scrambling (QIS) is a characteristic feature of several quantum systems.
We propose a novel and computationally efficient QIS quantifier based on a formulation of QIS in terms of quantum state discrimination.
We show that the optimal guessing probability, which reflects the degree of QIS induced by an isometric quantum evolution, is directly connected to the accessible min-information.
arXiv Detail & Related papers (2023-12-18T19:00:01Z) - 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) - Quantum benefit of the quantum equation of motion for the strongly
coupled many-body problem [0.0]
The quantum equation of motion (qEOM) is a hybrid quantum-classical algorithm for computing excitation properties of a fermionic many-body system.
We demonstrate explicitly that the qEOM exhibits a quantum benefit due to the independence of the number of required quantum measurements.
arXiv Detail & Related papers (2023-09-18T22:10:26Z) - Tomography of Quantum States from Structured Measurements via
quantum-aware transformer [12.506858276895915]
We study the structure of quantum measurements for characterizing a quantum state.
We design a quantum-aware transformer (QAT) model to capture the complex relationship between measured frequencies and density matrices.
In particular, we query quantum operators in the architecture to facilitate informative representations of quantum data.
arXiv Detail & Related papers (2023-05-09T13:22:13Z) - Quantum Merlin-Arthur proof systems for synthesizing quantum states [0.0]
We investigate a state synthesizing counterpart of the class NP-synthesizing.
We establish that the family of UQMA witnesses, considered as one of the most natural candidates, is in stateQMA.
We demonstrate that stateQCMA achieves perfect completeness.
arXiv Detail & Related papers (2023-03-03T12:14:07Z) - Efficient criteria of quantumness for a large system of qubits [58.720142291102135]
We discuss the dimensionless combinations of basic parameters of large, partially quantum coherent systems.
Based on analytical and numerical calculations, we suggest one such number for a system of qubits undergoing adiabatic evolution.
arXiv Detail & Related papers (2021-08-30T23:50:05Z) - Interactive Proofs for Synthesizing Quantum States and Unitaries [0.15229257192293197]
We study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations.
We define models of interactive proofs for quantum states and unitaries.
We obtain analogous results in the setting with multiple entangled provers as well.
arXiv Detail & Related papers (2021-08-16T15:59:33Z) - 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) - Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor.
We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
arXiv Detail & Related papers (2021-01-21T22:18:49Z) - Quantum information spreading in a disordered quantum walk [50.591267188664666]
We design a quantum probing protocol using Quantum Walks to investigate the Quantum Information spreading pattern.
We focus on the coherent static and dynamic disorder to investigate anomalous and classical transport.
Our results show that a Quantum Walk can be considered as a readout device of information about defects and perturbations occurring in complex networks.
arXiv Detail & Related papers (2020-10-20T20:03:19Z)
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.