Quantum independence and chromatic numbers

• URL: http://arxiv.org/abs/2401.16518v2
• Date: Wed, 7 Feb 2024 22:58:06 GMT
• Title: Quantum independence and chromatic numbers
• Authors: Chris Godsil, Mariia Sobchuk
• Abstract summary: We prove that for graphs with independence number is two, quantum and classical independence numbers coincide. We construct an infinite family of graphs whose quantum chromatic numbers are smaller than the classical chromatic numbers.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We construct a new graph on 120 vertices whose quantum and classical independence numbers are different. At the same time, we construct an infinite family of graphs whose quantum chromatic numbers are smaller than the classical chromatic numbers. Furthermore, we discover the relation to Kochen-Specker sets that characterizes quantum cocliques that are strictly bigger than classical ones. Finally, we prove that for graphs with independence number is two, quantum and classical independence numbers coincide.

Related papers

• Sufficient conditions for additivity of the zero-error classical capacity of quantum channels [2.733522537300566]
  The one-shot zero-error classical capacity of a quantum channel is equivalent to the multiplicativity of the independence number of the noncommutative graph.<n>We consider a block form of noncommutative graphs, and provide conditions when the independence number is multiplicative.
  arXiv  Detail & Related papers  (2026-01-26T14:45:23Z)
• Quantum Chromatic Number of Subgraphs of Orthogonality Graphs and the Distance-2 Hamming Graph [11.495969551409729]
  We extend the results by determining the exact quantum chromatic number of several subgraphs of the orthogonality graphs.<n>We also determine the quantum chromatic number of the distance-2 Hamming graph, whose edges consist of binary vectors of Hamming distance 2.
  arXiv  Detail & Related papers  (2025-12-01T02:21:25Z)
• High-dimensional graphs convolution for quantum walks photonic applications [41.94295877935867]
  We suggest a new method for lattices and hypercycle convolution that preserves quantum walk dynamics.<n>Our findings may be useful for saving a significant number of qubits required for algorithms that use quantum walk simulation on quantum devices.
  arXiv  Detail & Related papers  (2025-07-21T18:28:34Z)
• The Quantum Formalism Revisited [0.0]
  I discuss the structural elements of quantum mechanics with those of classical (statistical) mechanics.<n>Despite many amazing similarities, there are the well-known fundamental differences.
  arXiv  Detail & Related papers  (2025-06-19T17:25:40Z)
• On the Quantum Chromatic Gap [1.90365714903665]
  We put forth a quantum pseudo-telepathy version of Khot's $d$-to-$1$ Games Conjecture. We show that the existence of a certain form of pseudo-telepathic XOR games would imply the conjecture. We also prove that the Dinur--Khot--Kindler--Minzer--Safra reduction, recently used for proving the $2$-to-$2$ Games Theorem is quantum complete.
  arXiv  Detail & Related papers  (2025-03-29T20:10:34Z)
• Kochen-Specker for many qubits and the classical limit [55.2480439325792]
  It is shown that quantum and classical predictions converge as the number of qubits is increases to the macroscopic scale. This way to explain the classical limit concurs with, and improves, a result previously reported for GHZ states.
  arXiv  Detail & Related papers  (2024-11-26T22:30:58Z)
• Quantum Games and Synchronicity [0.0]
  We extend nonlocal games to allow quantum questions and answers. Equations are presented using a diagrammatic calculus for tensor categories. We extend the standard definitions, including strategies, correlations, and synchronicity.
  arXiv  Detail & Related papers  (2024-08-27T23:27:59Z)
• New Approaches to Complexity via Quantum Graphs [0.0]
  We introduce and study the clique problem for quantum graphs. inputs for our problems are presented as quantum channels induced by circuits. We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes $textsfNP$, $textsfMA$, $textsfQMA$, and $textsfQMA(2)$.
  arXiv  Detail & Related papers  (2023-09-22T14:20:14Z)
• Machine learning the dimension of a Fano variety [49.1574468325115]
  We show that a simple feed-forward neural network can determine the dimension of X. We also give positive evidence for the conjecture that the quantum period of a Fano variety determines that variety.
  arXiv  Detail & Related papers  (2023-09-11T14:13:30Z)
• 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 Instability [30.674987397533997]
  We show how a time-independent, finite-dimensional quantum system can give rise to a linear instability corresponding to that in the classical system. An unstable quantum system has a richer spectrum and a much longer recurrence time than a stable quantum system.
  arXiv  Detail & Related papers  (2022-08-05T19:53:46Z)
• Spectral bounds for the quantum chromatic number of quantum graphs [0.0]
  We obtain lower bounds for the classical and quantum number of a quantum graph using eigenvalues of the quantum adjacency matrix. We generalize all the spectral bounds given by Elphick and Wocjan to the quantum graph setting. Our results are achieved using techniques from linear algebra and a complete definition of quantum graph coloring.
  arXiv  Detail & Related papers  (2021-12-03T05:36:21Z)
• Equivalent Laplacian and Adjacency Quantum Walks on Irregular Graphs [0.0]
  The continuous-time quantum walk is a particle evolving by Schr"odinger's equation in discrete space. In some physical systems, however, the Hamiltonian is proportional to the adjacency matrix instead.
  arXiv  Detail & Related papers  (2021-07-12T16:59:06Z)
• On a tracial version of Haemers bound [20.98023024846862]
  We extend upper bounds on the quantum independence number and the quantum Shannon capacity of graphs to their counterparts in the commuting operator model. We call our bound the tracial Haemers bound, and we prove that it is multiplicative with respect to the strong product.
  arXiv  Detail & Related papers  (2021-07-06T12:09:33Z)
• Low temperature quantum bounds on simple models [0.0]
  Black-Hole models seem to saturate a set of quantum bounds on transport coefficients and chaos. This work aims to gain physical intuition about the quantum mechanisms that enforce these bounds on simple models. We show that the quantum dimensionless viscosity and the Lyapunov exponent only depend on the de Broglie length and a geometric length-scale.
  arXiv  Detail & Related papers  (2021-06-24T18:42:23Z)
• Synchronicity for quantum non-local games [0.7646713951724009]
  We show that quantum homomorphisms of quantum graphs can be viewed as entanglement assisted classical homomorphisms of the graphs. We give descriptions of the perfect quantum commuting and the perfect approximately quantum strategies for the quantum graph homomorphism game.
  arXiv  Detail & Related papers  (2021-06-22T02:40:41Z)
• Graph-Theoretic Framework for Self-Testing in Bell Scenarios [37.067444579637076]
  Quantum self-testing is the task of certifying quantum states and measurements using the output statistics solely. We present a new approach for quantum self-testing in Bell non-locality scenarios.
  arXiv  Detail & Related papers  (2021-04-27T08:15:01Z)
• Ruling out real-valued standard formalism of quantum theory [19.015836913247288]
  A quantum game has been developed to distinguish standard quantum theory from its real-number analog. We experimentally implement the quantum game based on entanglement swapping with a state-of-the-art fidelity of 0.952(1). Our results disprove the real-number formulation and establish the indispensable role of complex numbers in the standard quantum theory.
  arXiv  Detail & Related papers  (2021-03-15T03:56:13Z)

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.