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

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• 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)
• 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)
• On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
  We devise three effective QAE-based learning protocols to address three classically computational hard learning problems. Our work sheds new light on developing advanced quantum learning algorithms to accomplish hard quantum physics and quantum information processing tasks.
  arXiv  Detail & Related papers  (2021-06-29T14:01:40Z)
• 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.