A Quantum Algorithm For Computing Contextuality Bounds

• URL: http://arxiv.org/abs/2509.20250v1
• Date: Wed, 24 Sep 2025 15:36:02 GMT
• Title: A Quantum Algorithm For Computing Contextuality Bounds
• Authors: Colm Kelleher, Frédéric Holweck,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum contextuality is a limitation on deterministic hidden variable models, testable in measurement scenarios where outcomes differ under quantum or classical descriptions due to a common set of constraints. When considering measurements of $N$-qubit spin operators, constraints arise from commutation relations and classical bounds are determined by the $\textit{degree}$ of contextuality, an NP-hard quantity to compute in general, related to the larger class of optimisation problems known as $\texttt{MaxLin2}$. In this work we give a quantum algorithm based on Grover's search algorithm, computing the degree of contextuality in $O(\sqrt{n} \log\log{n})$ in $n$ states, a speedup over classical brute force method. We also study variations of Grover which encode the relevant information in the phases of the basis states, reducing circuit width and depth requirements with indicative complexity of $O(n^{\frac{1}{3}}(\log{n})^{2}\log\log{n})$. Testing on contemporary quantum backends with the IBM quantum experience gives inconclusive outputs due to noise-induced errors, an issue hopefully fixed by future hardware.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Non-Linear Transformations of Quantum Amplitudes: Exponential Improvement, Generalization, and Applications [0.0]
  Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems. We present a framework for applying a general class of non-linear functions to the amplitudes of quantum states. Our work provides an important and efficient building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.
  arXiv  Detail & Related papers  (2023-09-18T14:57:21Z)
• Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms [0.0]
  We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability. The algorithms achieve a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. An existing framework for using distributed version of Grover's search algorithm to accelerate triangle finding lies at the core of the speedup.
  arXiv  Detail & Related papers  (2023-04-06T02:18:52Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers [0.533024001730262]
  A classical vector $mathbfb$ is encoded in the amplitudes of a quantum state. An arbitrary state of $Q$ qubits generally requires approximately $2Q$ entangling gates. We present a deterministic (nonvariational) algorithm that allows one to flexibly reduce the quantum resources required for state preparation.
  arXiv  Detail & Related papers  (2021-10-26T07:37:54Z)
• Topological obstructions to quantum computation with unitary oracles [0.0]
  Some tasks are impossible in quantum circuits, although their classical versions are easy, for example, cloning. We show limitations of process tomography, oracle neutralization, and $sqrt[dim U]U$, $UT$, and $Udagger$ algorithms. Our results strengthen an advantage of linear optics, challenge the experiments on relaxed causality, and motivate new algorithms with many-outcome measurements.
  arXiv  Detail & Related papers  (2020-11-19T18:52: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.