How much classical information is carried by a quantum state? An approach inspired by Kolmogorov complexity

• URL: http://arxiv.org/abs/2204.02370v2
• Date: Fri, 8 Apr 2022 10:06:13 GMT
• Title: How much classical information is carried by a quantum state? An approach inspired by Kolmogorov complexity
• Authors: Doriano Brogioli
• Abstract summary: I give a definition of the (classical) information content of a quantum state. I show that, for some well-known quantum circuits, the information content of the output state is evaluated in the number of qubits. On the other hand, applying known results, it is possible to devise quantum circuits that generate much more complex states.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In quantum mechanics, a state is an element of a Hilbert space whose dimension exponentially grows with the increase of the number of particles (or qubits, in quantum computing). The vague question "is this huge Hilbert space really there?" has been rigorously formalized inside the computational complexity theory; the research suggests a positive answer to the question. Along this line, I give a definition of the (classical) information content of a quantum state, taking inspiration from the Kolmogorov complexity. I show that, for some well-known quantum circuits (having a number of gates polynomial in the number of qubits), the information content of the output state, evaluated according to my definition, is polynomial in the number of qubits. On the other hand, applying known results, it is possible to devise quantum circuits that generate much more complex states, having an exponentially-growing information content. A huge amount of classical information can be really present inside a quantum state, however, I show that this property is not necessarily exploited by quantum computers, not even by quantum algorithms showing an exponential speed-up with respect to classical computation.

Related papers

• Quantum Information Processing with Molecular Nanomagnets: an introduction [49.89725935672549]
  We provide an introduction to Quantum Information Processing, focusing on a promising setup for its implementation. We introduce the basic tools to understand and design quantum algorithms, always referring to their actual realization on a molecular spin architecture. We present some examples of quantum algorithms proposed and implemented on a molecular spin qudit hardware.
  arXiv  Detail & Related papers  (2024-05-31T16:43:20Z)
• What is computable and non-computable in the quantum domain: 7 statements and 3 conjectures [0.7892577704654171]
  There is no universal approach that helps to define a scope of problems that quantum computers are able to speed up. On the one hand, the class of quantum states that is of interest for quantum computing should be complex. On the other hand, such quantum states should be reachable on a practical quantum computer.
  arXiv  Detail & Related papers  (2024-03-25T15:47:35Z)
• Quantum data learning for quantum simulations in high-energy physics [55.41644538483948]
  We explore the applicability of quantum-data learning to practical problems in high-energy physics. We make use of ansatz based on quantum convolutional neural networks and numerically show that it is capable of recognizing quantum phases of ground states. The observation of non-trivial learning properties demonstrated in these benchmarks will motivate further exploration of the quantum-data learning architecture in high-energy physics.
  arXiv  Detail & Related papers  (2023-06-29T18:00:01Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Quantum walks on random lattices: Diffusion, localization and the absence of parametric quantum speed-up [0.0]
  We study propagation of quantum walks on percolation-generated two-dimensional random lattices. We show that even arbitrarily weak concentrations of randomly removed lattice sites give rise to a complete breakdown of the superdiffusive quantum speed-up. The fragility of quantum speed-up implies dramatic limitations for quantum information applications of quantum walks on random geometries and graphs.
  arXiv  Detail & Related papers  (2022-10-11T10:07:52Z)
• Quantum information and beyond -- with quantum candies [0.0]
  We investigate, extend, and greatly expand here "quantum candies" (invented by Jacobs) "quantum" candies describe some basic concepts in quantum information, including quantum bits, complementarity, the no-cloning principle, and entanglement. These demonstrations are done in an approachable manner, that can be explained to high-school students, without using the hard-to-grasp concept of superpositions and its mathematics.
  arXiv  Detail & Related papers  (2021-09-30T16:05:33Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Quantum Oracle Separations from Complex but Easily Specified States [1.52292571922932]
  A quantum oracle is a black box unitary callable during quantum computation. We constrain the marked state in ways that make it easy to specify classically while retaining separations in task complexity. Using the fact that classically defined oracle may enable a quantum algorithm to prepare an otherwise hard state in steps, we observe quantum-classical oracle separation in heavy output sampling.
  arXiv  Detail & Related papers  (2021-04-15T05:40:38Z)
• Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
  We show that the advantage of quantum kernels is vanished for large size datasets, few number of measurements, and large system noise. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
  arXiv  Detail & Related papers  (2021-03-31T02:41:36Z)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems. We propose an algorithm to implement imaginary time propagation on a quantum computer.
  arXiv  Detail & Related papers  (2021-02-24T12:48:00Z)
• Characterization of quantum states based on creation complexity [0.0]
  The creation complexity of a quantum state is the minimum number of elementary gates required to create it from a basic initial state. We show for an entirely general quantum state it is exponentially hard (requires a number of steps that scales exponentially with the number of qubits) to determine if the creation complexity is. We then show it is possible for a large class of quantum states with creation complexity to have common coefficient features such that given any candidate quantum state we can design an efficient coefficient sampling procedure to determine if it belongs to the class or not with arbitrarily high success probability.
  arXiv  Detail & Related papers  (2020-04-28T21:12:45Z)

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.