Algebraic paradoxes in adaptive quantum computation

• URL: http://arxiv.org/abs/2607.26157v1
• Date: Tue, 28 Jul 2026 18:06:08 GMT
• Title: Algebraic paradoxes in adaptive quantum computation
• Abstract summary: Measurement-based quantum computation (MBQC) is a universal model of quantum computation whose full power requires adaptivity.<n>We show that if an adaptive $mathbbZ$-textual measurement-based quantum computing protocol deterministically computes a non-affine function, the underlying quantum resource satisfies an inconsistent set of linear equations.
• Score: 0.1399948157377307
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Measurement-based quantum computation (MBQC) is a universal model of quantum computation whose full power requires adaptivity. Contextuality is known to power quantum advantage in MBQC, yet it has resisted algebraic analysis in the adaptive setting. We show that if an adaptive $\mathbb{Z}_2$-linear measurement-based quantum computing protocol deterministically computes a non-affine Boolean function, then the underlying quantum resource satisfies an inconsistent set of linear equations. This witnesses an algebraic form of strong contextuality generalising Mermin's All-versus-Nothing arguments. Such algebraic contextuality can be detected cohomologically, resolving an open question posed by Raussendorf, who had established cohomological witnesses of contextuality for non-adaptive protocols, but left the adaptive case open. We prove this result constructively: we model adaptive measurement protocols as ordinary measurements on a larger scenario of tree-like measurements, and explicitly build the inconsistent equations inductively.

Related papers

• Simulating Supersymmetric Quantum Mechanics Using Variational Quantum Algorithms [0.0]
  We present the variational quantum eigensolver (VQE) for supersymmetric quantum mechanics with various superpotentials.<n>A key new feature is an adaptive ansatz construction algorithm that reduces the number of variational parameters within our anstze.<n>Preliminary VQE results obtained from real IBM quantum devices highlight accuracy, resource constraints, and computational cost.
  arXiv  Detail & Related papers  (2026-03-19T10:54:58Z)
• Quantum Homotopy Algorithm for Solving Nonlinear PDEs and Flow Problems [0.0]
  Quantum algorithms to integrate nonlinear PDEs governing flow problems are challenging to discover but critical to enhancing the practical usefulness of quantum computing.<n>We present here a near-optimal, robust, and end-to-end quantum algorithm to solve time-dependent, dissipative, and nonlinear PDEs.
  arXiv  Detail & Related papers  (2025-12-24T07:56:34Z)
• Performance Guarantees for Quantum Neural Estimation of Entropies [31.955071410400947]
  Quantum neural estimators (QNEs) combine classical neural networks with parametrized quantum circuits.<n>We study formal guarantees for QNEs of measured relative entropies in the form of non-asymptotic error risk bounds.<n>Our theory aims to facilitate principled implementation of QNEs for measured relative entropies.
  arXiv  Detail & Related papers  (2025-11-24T16:36:06Z)
• Quantum algorithms for equational reasoning [0.0]
  We introduce quantum normal form reduction, a quantum computational framework for analyzing symbolic expressions.<n>We demonstrate a quantum-inspired version of the algorithm using tensor network simulations.<n>This framework opens the path for quantum symbolic computation in areas ranging from quantum and logical circuit design to data compression.
  arXiv  Detail & Related papers  (2025-08-28T18:00:06Z)
• Quantum computer formulation of the FKP-operator eigenvalue problem for probabilistic learning on manifolds [0.0]
  We present a quantum computing formulation to address a challenging problem in the development of probabilistic learning on manifold (PLoM)<n>It involves solving the spectral problem of the high-dimensional Fokker-Planck operator, which remains beyond the reach of classical computing.<n>Explicit formulas for the Laplacian and potential are derived and mapped onto qubits using Pauli matrix expressions.
  arXiv  Detail & Related papers  (2025-02-20T14:05:16Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Solving reaction dynamics with quantum computing algorithms [42.408991654684876]
  We study quantum algorithms for response functions, relevant for describing different reactions governed by linear response.<n>We focus on nuclear-physics applications and consider a qubit-efficient mapping on the lattice, which can efficiently represent the large volumes required for realistic scattering simulations.
  arXiv  Detail & Related papers  (2024-03-30T00:21:46Z)
• Determining the ability for universal quantum computing: Testing controllability via dimensional expressivity [39.58317527488534]
  Controllability tests can be used in the design of quantum devices to reduce the number of external controls. We devise a hybrid quantum-classical algorithm based on a parametrized quantum circuit.
  arXiv  Detail & Related papers  (2023-08-01T15:33:41Z)
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory [44.99833362998488]
  We introduce quantum algorithms that can efficiently simulate certain classes of interactions consisting of correlated changes in multiple quantum numbers. The lattice gauge theory studied is the SU(2) gauge theory in 1+1 dimensions coupled to one flavor of staggered fermions. The algorithms are shown to be applicable to higher-dimensional theories as well as to other Abelian and non-Abelian gauge theories.
  arXiv  Detail & Related papers  (2022-12-28T18:56:25Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)

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.