Bounding the Graph Capacity with Quantum Mechanics and Finite Automata

• URL: http://arxiv.org/abs/2403.10985v1
• Date: Sat, 16 Mar 2024 17:41:01 GMT
• Title: Bounding the Graph Capacity with Quantum Mechanics and Finite Automata
• Authors: Alexander Meiburg,
• Abstract summary: The zero-error capacity of a channel quantifies how much information can be transmitted with no risk of error. In contrast to the Shannon capacity of a channel, the zero-error capacity has not even been shown to be computable. We show that the unitary capacity is within a controllable factor of the zero-error capacity.
• Score: 55.2480439325792
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The zero-error capacity of a channel (or Shannon capacity of a graph) quantifies how much information can be transmitted with no risk of error. In contrast to the Shannon capacity of a channel, the zero-error capacity has not even been shown to be computable: we have no convergent upper bounds. In this work, we present a new quantity, the zero-error {\em unitary} capacity, and show that it can be succinctly represented as the tensor product value of a quantum game. By studying the structure of finite automata, we show that the unitary capacity is within a controllable factor of the zero-error capacity. This allows new upper bounds through the sum-of-squares hierarchy, which converges to the commuting operator value of the game. Under the conjecture that the commuting operator and tensor product value of this game are equal, this would yield an algorithm for computing the zero-error capacity.

Related papers

• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• A condition for the zero-error capacity of quantum channels [0.0]
  We present a condition for the zero-error capacity of quantum channels. We first prove that the eigenvectors common to the Kraus operators representing the quantum channel are fixed points of the channel.
  arXiv  Detail & Related papers  (2023-12-20T20:18:51Z)
• Calculating the many-body density of states on a digital quantum computer [58.720142291102135]
  We implement a quantum algorithm to perform an estimation of the density of states on a digital quantum computer. We use our algorithm to estimate the density of states of a non-integrable Hamiltonian on the Quantinuum H1-1 trapped ion chip for a controlled register of 18bits.
  arXiv  Detail & Related papers  (2023-03-23T17:46:28Z)
• Non-Abelian braiding of graph vertices in a superconducting processor [144.97755321680464]
  Indistinguishability of particles is a fundamental principle of quantum mechanics. braiding of non-Abelian anyons causes rotations in a space of degenerate wavefunctions. We experimentally verify the fusion rules of the anyons and braid them to realize their statistics.
  arXiv  Detail & Related papers  (2022-10-19T02:28:44Z)
• Topological Quantum Computation on Supersymmetric Spin Chains [0.0]
  Quantum gates built out of braid group elements form the building blocks of topological quantum computation. We show that the fusion spaces of anyonic systems can be precisely mapped to the product state zero modes of certain Nicolai-like supersymmetric spin chains.
  arXiv  Detail & Related papers  (2022-09-08T13:52:10Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Sub-bosonic (deformed) ladder operators [62.997667081978825]
  We present a class of deformed creation and annihilation operators that originates from a rigorous notion of fuzziness. This leads to deformed, sub-bosonic commutation relations inducing a simple algebraic structure with modified eigenenergies and Fock states. In addition, we investigate possible consequences of the introduced formalism in quantum field theories, as for instance, deviations from linearity in the dispersion relation for free quasibosons.
  arXiv  Detail & Related papers  (2020-09-10T20:53:58Z)
• Quantum capacity of bosonic dephasing channel [0.0]
  We study the quantum capacity of continuous variable dephasing channel, which is a notable example of non-Gaussian quantum channel. We consider input energy restriction and show that by increasing it, the capacity saturates to a finite value.
  arXiv  Detail & Related papers  (2020-07-08T04:56:33Z)
• The Haemers bound of noncommutative graphs [10.293135569592833]
  We show that the Haemers bound upper bounds the Shannon capacity of noncommutative graphs. We also show that it can outperform other known upper bounds, including noncommutative analogues of the Lov'asz theta function.
  arXiv  Detail & Related papers  (2020-02-07T12:46:39Z)

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.