On the Quantum Chromatic Gap

• URL: http://arxiv.org/abs/2503.23207v1
• Date: Sat, 29 Mar 2025 20:10:34 GMT
• Title: On the Quantum Chromatic Gap
• Authors: Lorenzo Ciardo,
• Abstract summary: We put forth a quantum pseudo-telepathy version of Khot's $d$-to-$1$ Games Conjecture.<n>We show that the existence of a certain form of pseudo-telepathic XOR games would imply the conjecture.<n>We also prove that the Dinur--Khot--Kindler--Minzer--Safra reduction, recently used for proving the $2$-to-$2$ Games Theorem is quantum complete.
• Score: 1.90365714903665
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The largest known gap between quantum and classical chromatic number of graphs, obtained via quantum protocols for colouring Hadamard graphs based on the Deutsch--Jozsa algorithm and the quantum Fourier transform, is exponential. We put forth a quantum pseudo-telepathy version of Khot's $d$-to-$1$ Games Conjecture and prove that, conditional to its validity, the gap is unbounded: There exist graphs whose quantum chromatic number is $3$ and whose classical chromatic number is arbitrarily large. Furthermore, we show that the existence of a certain form of pseudo-telepathic XOR games would imply the conjecture and, thus, the unboundedness of the quantum chromatic gap. As two technical steps of our proof that might be of independent interest, we establish a quantum adjunction theorem for Pultr functors between categories of relational structures, and we prove that the Dinur--Khot--Kindler--Minzer--Safra reduction, recently used for proving the $2$-to-$2$ Games Theorem, is quantum complete.

Related papers

• 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)
• The multimode conditional quantum Entropy Power Inequality and the squashed entanglement of the extreme multimode bosonic Gaussian channels [53.253900735220796]
  Inequality determines the minimum conditional von Neumann entropy of the output of the most general linear mixing of bosonic quantum modes. Bosonic quantum systems constitute the mathematical model for the electromagnetic radiation in the quantum regime.
  arXiv  Detail & Related papers  (2024-10-18T13:59:50Z)
• Krenn-Gu conjecture for sparse graphs [0.22499166814992438]
  Greenberger-Horne-Zeilinger (GHZ) states are quantum states involving at least three entangled particles. GHZ states are of fundamental interest in quantum information theory, and the construction of such states of high dimension has various applications in quantum communication and cryptography.
  arXiv  Detail & Related papers  (2024-06-29T03:51:14Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Quantum soft-covering lemma with applications to rate-distortion coding, resolvability and identification via quantum channels [7.874708385247353]
  We prove a one-shot quantum covering lemma in terms of smooth min-entropies. We provide new upper bounds on the unrestricted and simultaneous identification capacities of quantum channels.
  arXiv  Detail & Related papers  (2023-06-21T17:53:22Z)
• A vertical gate-defined double quantum dot in a strained germanium double quantum well [48.7576911714538]
  Gate-defined quantum dots in silicon-germanium heterostructures have become a compelling platform for quantum computation and simulation. We demonstrate the operation of a gate-defined vertical double quantum dot in a strained germanium double quantum well. We discuss challenges and opportunities and outline potential applications in quantum computing and quantum simulation.
  arXiv  Detail & Related papers  (2023-05-23T13:42:36Z)
• 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)
• 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)
• 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)
• Lattice Gauge Theory for a Quantum Computer [0.0]
  Hamiltonian was introduced two decades ago as an alternative to Wilson's Euclidean lattice QCD with gauge fields represented by bi-linear fermion/anti-fermion operators. D-theory leads naturally to quantum Qubit algorithms. Digital quantum computing for gauge theories, the simplest example of U(1) compact QED on triangular lattice is defined.
  arXiv  Detail & Related papers  (2020-02-24T01:16:49Z)

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.