The quantum Ramsey numbers $QR(2,k)$

• URL: http://arxiv.org/abs/2507.04128v2
• Date: Tue, 08 Jul 2025 17:13:57 GMT
• Title: The quantum Ramsey numbers $QR(2,k)$
• Authors: Andrew Allen, Andre Kornell,
• Abstract summary: Operator systems of matrices can be viewed as quantum analogues of finite graphs.<n>We determine the quantum Ramsey numbers $QR(2,k)$ and the lower quantum Tur'an numbers $Tdownarrow(n, m)$ with $m geq n/4$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Operator systems of matrices can be viewed as quantum analogues of finite graphs. This analogy suggests many natural combinatorial questions in linear algebra. We determine the quantum Ramsey numbers $QR(2,k)$ and the lower quantum Tur\'an numbers $T^\downarrow(n, m)$ with $m \geq n/4$. In particular, we conclude that $QR(2,2) = 4$ and confirm Weaver's conjecture that $T^\downarrow(4, 1) = 4$. We also obtain a new result for the existence of anticliques in quantum graphs of low dimension.

Related papers

• Scaling of symmetry-restricted quantum circuits [42.803917477133346]
  In this work, we investigate the properties of $mathcalMSU(2N)$, $mathcalM$-invariant subspaces of the special unitary Lie group $SU(2N)$.
  arXiv  Detail & Related papers  (2024-06-14T12:12:15Z)
• Achieving quantum advantage in a search for a violations of the Goldbach conjecture, with driven atoms in tailored potentials [15.236546465767026]
  Goldbach conjecture states that any even natural number $N$ greater than $2$ can be written as the sum of two prime numbers $ptext(I)$ and $ptext(II)$.<n>In this article we propose a quantum analogue device that solves the problem.
  arXiv  Detail & Related papers  (2024-03-31T01:29:16Z)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  We focus on learning mixtures of separated Gaussians on $mathbbRd$ of the form $P= sum_i=1k w_i mathcalN(boldsymbol mu_i,mathbf Sigma_i)$. We prove that any Statistical Query (SQ) algorithm for this problem requires complexity at least $dOmega (1/epsilon)$.
  arXiv  Detail & Related papers  (2023-06-22T17:23:36Z)
• On the moments of random quantum circuits and robust quantum complexity [0.0]
  We prove new lower bounds on the growth of robust quantum circuit complexity. We show two bounds for random quantum circuits with local gates drawn from a subgroup of $SU(4)$.
  arXiv  Detail & Related papers  (2023-03-29T18:06:03Z)
• Quantum Mass Production Theorems [0.22843885788439797]
  We prove that for any $n$-qubit unitary transformation $U$ there exists a quantum circuit to implement $Uotimes r$ with at most $O(4n)$ gates. We also establish results for quantum states and diagonal unitary transformations.
  arXiv  Detail & Related papers  (2022-12-29T18:13:44Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• A quantum number theory [0.0]
  We build our QNT by defining pure quantum number operators ($q$-numbers) of a Hilbert space that generate classical numbers ($c$-numbers) belonging to discrete Euclidean spaces. The eigenvalues of each $textbfZ$ component generate a set of classical integers $m in mathbbZcup frac12mathbbZ*$, $mathbbZ* = mathbbZ*$, albeit all components do not generate $mathbbZ3
  arXiv  Detail & Related papers  (2021-08-18T17:26:03Z)
• Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically [36.685393265844986]
  We construct new families of quantum error correction codes achieving the quantum-Omega-Varshamov boundally. $mathscrQ$ can be encoded very efficiently by circuits of size $O(N)$ and depth $O(sqrtN)$. $mathscrQ$ can also be decoded in parallel in $O(sqrtN)$ time by using $O(sqrtN)$ classical processors.
  arXiv  Detail & Related papers  (2021-07-12T03:27:30Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Quantum Implications of Huang's Sensitivity Theorem [4.970364068620607]
  We show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity. We also use the result to resolve the quantum analogue of the Aanderaa-Karp-Rosenberg conjecture.
  arXiv  Detail & Related papers  (2020-04-28T00:54:23Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

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.