Robust Quantum Memory Advantage from Contextuality

• URL: http://arxiv.org/abs/2607.00507v1
• Date: Wed, 01 Jul 2026 06:42:59 GMT
• Title: Robust Quantum Memory Advantage from Contextuality
• Abstract summary: We show an exponential, noise-resilient memory advantage for quantum finite automata arising from graph-theoretic approaches to contextuality.<n>This memory advantage maintains an $mathcalO(1)$ threshold against both depolarizing and coherent noise.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum contextuality is widely recognized as an essential non-classical resource underlying quantum technology, yet illuminating the precise mechanisms through which it translates into unconditional computational advantages remains an ongoing challenge. We demonstrate an exponential, noise-resilient memory advantage for quantum finite automata arising from graph-theoretic approaches to contextuality. We define a promise problem on an exclusivity graph $G$ for which any classical deterministic automaton acts as a non-contextual hidden variable model requiring at least $N=χ(G)$ states, where $χ(G)$ is the graph's chromatic number. In contrast, by exploiting a structural phenomenon we term \textit{representational contextuality}, a QFA solves this task using a memory of dimension at most $d=ξ(G)+1$, where $ξ(G)$ is the graph's orthogonal rank. This separation scales exponentially ($d=\mathcal O(n)$ versus $N=2^{Ω(n)}$) for Boolean-orthogonality graphs. Crucially, this memory advantage maintains an $\mathcal{O}(1)$ threshold against both depolarizing and coherent noise.

Related papers

• Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid [31.45779401617503]
  Knaster-Tarski fixed-point theorem states that every monotone function over a complete lattice has a fixed point.<n>We prove an $(klog n)$ quantum query lower bound for finding a fixed point of a monotone function on $[n]k$, using the nonnegative spectral adversary method.
  arXiv  Detail & Related papers  (2026-09-03T13:06:12Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  For Hamiltonian $H = sum_j h_j$, we proveally tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer.<n>Our hold for arbitrary term norms $|h_j|$, time $t$, and trace-distance error $$.
  arXiv  Detail & Related papers  (2026-07-22T07:41:32Z)
• The Marginal Problem for Density Operators [0.30079490585515334]
  We study when local reduced density operators can be assembled into a global quantum state with a prescribed Markov structure.<n>We prove that this obstruction is captured exactly by a trace condition.<n>Three-qubit Pauli examples show that the quantum obstructions are real.
  arXiv  Detail & Related papers  (2026-05-19T07:06:54Z)
• Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition [29.68432646391692]
  Quantum channel tomography is a fundamental task in the characterization and validation of quantum hardware.<n>Despite extensive prior work, the optimal query complexity for quantum channel tomography is far from fully understood.<n>We show that in the near-boundary regime, the query complexity exhibits a mixture of Heisenberg and classical scaling behaviors.
  arXiv  Detail & Related papers  (2026-04-19T10:51:10Z)
• A Quantum Algorithm For Computing Contextuality Bounds [0.0]
  We give a quantum algorithm based on Grover's search algorithm, computing the degree of contextuality in $O(sqrtn loglogn)$ in $n$ states, a speedup over classical brute force method.<n>We also study variations of Grover which encode the relevant information in the phases of the basis states, reducing circuit width and depth requirements.
  arXiv  Detail & Related papers  (2025-09-24T15:36:02Z)
• Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD.<n>Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers.<n>Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used quantum machines.
  arXiv  Detail & Related papers  (2024-04-30T23:55:03Z)
• Quantum advantage in zero-error function computation with side information [10.0060346233449]
  We consider the problem of zero-error function computation with side information.<n>Alice and Bob have correlated sources $X,Y$ with joint p.m.f. $p_XY(cdot, cdot)$. Bob wants to calculate $f(X,Y)$ with zero error.
  arXiv  Detail & Related papers  (2024-02-02T16:41:36Z)
• Adversarial Quantum Machine Learning: An Information-Theoretic Generalization Analysis [39.889087719322184]
  We study the generalization properties of quantum classifiers adversarially trained against bounded-norm white-box attacks. We derive novel information-theoretic upper bounds on the generalization error of adversarially trained quantum classifiers.
  arXiv  Detail & Related papers  (2024-01-31T21:07:43Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
  arXiv  Detail & Related papers  (2023-08-16T17:54:56Z)
• No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
  We give an almost complete characterization of the hardness of $c$-coloring $chi$-chromatic graphs with distributed algorithms. We show that these problems do not admit any distributed quantum advantage.
  arXiv  Detail & Related papers  (2023-07-18T17:17:27Z)
• The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs [6.305950347749109]
  We introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs.
  arXiv  Detail & Related papers  (2021-10-08T15:24:31Z)
• Quantum scrambling of observable algebras [0.0]
  quantum scrambling is defined by how the associated physical degrees of freedom get mixed up with others by the dynamics. This is accomplished by introducing a measure, the geometric algebra anti-correlator (GAAC) of the self-orthogonalization of the commutant of $cal A$ induced by the dynamics. For generic energy spectrum we find explicit expressions for the infinite-time average of the GAAC which encode the relation between $cal A$ and the full system of Hamiltonian eigenstates.
  arXiv  Detail & Related papers  (2021-07-02T14:30:58Z)
• 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 Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.