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

• 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)
• Equivariant simplicial distributions and quantum contextuality [0.0]
  We introduce an equivariant version of contextuality with respect to a symmetry group, which comes with natural applications to quantum theory. In the equivariant setting, we construct cohomology classes that can detect contextuality.
  arXiv  Detail & Related papers  (2023-10-27T13:25:46Z)
• 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)
• A Unified Theory of Barren Plateaus for Deep Parametrized Quantum Circuits [37.84307089310829]
  Variational quantum computing schemes have received considerable attention due to their high versatility and potential to make practical use of near-term quantum devices. At their core, these models train a loss function by sending an initial state through a parametrized quantum circuit, and evaluating the expectation value of some operator at the circuit's output. Despite their promise, the trainablity of these algorithms is hindered by barren plateaus induced by the expressiveness of the parametrized quantum circuit, entanglement of the input data, the locality of the observable, or the presence of hardware noise.
  arXiv  Detail & Related papers  (2023-09-17T18:14:10Z)
• 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)
• Routed quantum circuits [0.0]
  We argue that the quantum-theoretical structures studied in several recent lines of research cannot be adequately described within the standard framework of quantum circuits. We propose an extension to the framework of quantum circuits, given by textitrouted linear maps and textitrouted quantum circuits
  arXiv  Detail & Related papers  (2020-11-16T17:31:56Z)
• 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.