Comparing two cohomological obstructions for contextuality, and a generalised construction of quantum advantage with shallow circuits

• URL: http://arxiv.org/abs/2212.09382v1
• Date: Mon, 19 Dec 2022 11:43:37 GMT
• Title: Comparing two cohomological obstructions for contextuality, and a generalised construction of quantum advantage with shallow circuits
• Authors: Sivert Aasn{\ae}ss
• Abstract summary: We show that a restricted class of quantum circuits is more powerful than its classical analogue. A class of circuits of bounded depth and fan-in (shallow circuits) exploits a particular family of examples of contextuality. A systematic way of taking examples of contextuality and producing unconditional quantum advantage results with shallow circuits.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present two results on the subject of quantum contextuality and cohomology, and non-locality and quantum advantage with shallow circuits. Abramsky et al. showed that a range of examples of quantum contextuality is detected by a cohomological invariant based on \v{C}ech cohomology. However, the approach does not give a complete cohomological characterisation of contextuality. A different cohomological approach to contextuality was introduced by Okay et al. Their approach exploits the algebraic structure of the Pauli operators and their qudit generalisations known as Weyl operators. We give an abstract account of this structure, then generalise their approach to any example of contextuality with this structure. We prove at this general level that the approach does not give a more complete characterisation of contextuality than the \v{C}ech cohomology approach. Bravyi, Gosset, and K\"{o}nig (BGK) gave the first unconditional proof that a restricted class of quantum circuits is more powerful than its classical analogue. The result, for the class of circuits of bounded depth and fan-in (shallow circuits), exploits a particular family of examples of contextuality. BGK's quantum circuit and computational problem are derived from a family of non-local games related to the well-known GHZ non-local game. We present a generalised version of their construction. A systematic way of taking examples of contextuality and producing unconditional quantum advantage results with shallow circuits.

Related papers

• Benefiting from Quantum? A Comparative Study of Q-Seg, Quantum-Inspired Techniques, and U-Net for Crack Segmentation [41.01256771536732]
  This study evaluates the performance of quantum and quantum-inspired methods compared to classical models for crack segmentation. Our results indicate that quantum-inspired and quantum methods offer a promising alternative for image segmentation, particularly for complex crack patterns, and could be applied in near-future applications.
  arXiv  Detail & Related papers  (2024-10-14T16:51:59Z)
• Exploring Quantum Contextuality with the Quantum Moebius-Escher-Penrose hypergraph [0.0]
  This study presents the quantum Moebius-Escher-Penrose hypergraph, drawing inspiration from paradoxical constructs such as the Moeobius strip and Penrose's impossible objects'
  arXiv  Detail & Related papers  (2024-09-16T11:17:53Z)
• An algebraic characterisation of Kochen-Specker contextuality [0.0]
  Contextuality is a key distinguishing feature between classical and quantum physics. It expresses a fundamental obstruction to describing quantum theory using classical concepts. Different frameworks address different aspects of the phenomenon, yet their precise relationship often remains unclear.
  arXiv  Detail & Related papers  (2024-08-29T17:58:12Z)
• A computational test of quantum contextuality, and even simpler proofs of quantumness [43.25018099464869]
  We show that an arbitrary contextuality game can be compiled into an operational "test of contextuality" involving a single quantum device. Our work can be seen as using cryptography to enforce spatial separation within subsystems of a single quantum device.
  arXiv  Detail & Related papers  (2024-05-10T19:30:23Z)
• Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
  Quantum Circuits (PQCs) are still not fully understood outside the scope of their principal application. We analyse the generation of random states in PQCs under restrictions on the qubits connectivities. We place a connection between how steep is the increase on the uniformity of the distribution of the generated states and the generation of entanglement.
  arXiv  Detail & Related papers  (2024-05-03T17:32:55Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• 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)
• The logic of contextuality [0.0]
  Contextuality is a key signature of quantum non-classicality. We study the logic of contextuality in the setting of partial Boolean algebras.
  arXiv  Detail & Related papers  (2020-11-05T19:04:04Z)
• Relevant OTOC operators: footprints of the classical dynamics [68.8204255655161]
  The OTOC-RE theorem relates the OTOCs summed over a complete base of operators to the second Renyi entropy. We show that the sum over a small set of relevant operators, is enough in order to obtain a very good approximation for the entropy. In turn, this provides with an alternative natural indicator of complexity, i.e. the scaling of the number of relevant operators with time.
  arXiv  Detail & Related papers  (2020-07-31T19:23:26Z)
• A Quantum G\"odelian Hunch [0.0]
  This essay aims at arguing for such G"odelian hunch via two case studies. The theological motivational origin of quantum contextuality is introduced in order to show how this result might be related to a Liar-like undecidability. A personal analysis of the related Wigner's friend thought experiment and and a recent paradox by Frauchiger and Renner is presented.
  arXiv  Detail & Related papers  (2020-05-07T11:22:20Z)
• Cohomology and the Algebraic Structure of Contextuality in Measurement Based Quantum Computation [0.0]
  Roberts, Bartlett and Raussendorf recently introduced a new cohomological approach to contextuality in quantum computation. We give an abstract description of their obstruction and the algebraic structure it exploits, using the sheaf theoretic framework of Abramsky and Brandenburger. At this level of generality we contrast their approach to the Cech cohomology obstruction of Abramsky, Mansfield and Barbosa and give a direct proof that Cech cohomology is at least as powerful.
  arXiv  Detail & Related papers  (2020-05-01T04:15:23Z)

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.