Unconditional quantum MAGIC advantage in shallow circuit computation

• URL: http://arxiv.org/abs/2402.12246v1
• Date: Mon, 19 Feb 2024 15:59:48 GMT
• Title: Unconditional quantum MAGIC advantage in shallow circuit computation
• Authors: Xingjian Zhang, Zhaokai Pan, Guoding Liu
• Abstract summary: We show that the magic advantage can be unconditionally established, at least in a shallow circuit with a constant depth. We construct a specific nonlocal game inspired by the linear binary constraint system. We also provide an efficient algorithm to aid the search for potential magic-requiring nonlocal games.
• Score: 2.8289044717329905
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum theory promises computation speed-ups than classical means. The full power is believed to reside in "magic" states, or equivalently non-Clifford operations -- the secret sauce to establish universal quantum computing. Despite the celebrated Gottesman-Knill Theorem stating that magic-free computation can be efficiently simulated by a classical computer, it is still questionable whether "magic" is really magical. Indeed, all the existing results establish its supremacy for efficient computation upon unproven complexity assumptions or queries to black-box oracles. In this work, we show that the magic advantage can be unconditionally established, at least in a shallow circuit with a constant depth. For this purpose, we first construct a specific nonlocal game inspired by the linear binary constraint system, which requires the magic resource to generate the desired nonlocal statistics or quantum "pseudo telepathy." For a relation problem targeting generating such correlations between arbitrary nonlocal computation sites, we construct a shallow circuit with bounded fan-in gates that takes the strategy for quantum pseudo telepathy as a sub-routine to solve the problem with certainty. In contrast, magic-free counterparts inevitably require a logarithmic circuit depth to the input size, and the separation is proven optimal. As by-products, we prove that the nonlocal game we construct has non-unique perfect winning strategies, answering an open problem in quantum self-testing. We also provide an efficient algorithm to aid the search for potential magic-requiring nonlocal games similar to the current one. We anticipate our results to enlighten the ultimate establishment of the unconditional advantage of universal quantum computation.

Related papers

• Quantum magic dynamics in random circuits [1.9568111750803001]
  Magic refers to the degree of "quantumness" in a system that cannot be fully described by stabilizer states and Clifford operations alone. In quantum computing, stabilizer states and Clifford operations can be efficiently simulated on a classical computer.
  arXiv  Detail & Related papers  (2024-10-28T15:29:21Z)
• Phase transition in magic with random quantum circuits [1.3551232282678036]
  We observe that a random stabilizer code subject to coherent errors exhibits a phase transition in magic. A better understanding of such rich behavior in the resource theory of magic could shed more light on origins of quantum speedup.
  arXiv  Detail & Related papers  (2023-04-20T17:29:45Z)
• Grover's Algorithm Offers No Quantum Advantage [0.0]
  Grover's algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. We construct a quantum inspired algorithm, executable on a classical computer, that performs Grover's task in linear number of call to the oracle. We critically examine the possibility of a practical speedup, a possibility that depends on the nature of the quantum circuit associated with the oracle.
  arXiv  Detail & Related papers  (2023-03-20T17:56:20Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• 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)
• Measuring magic on a quantum processor [5.639451539396458]
  We propose and experimentally demonstrate a protocol for measuring magic based on randomized measurements. This protocol can provide a characterization of the effectiveness of a quantum hardware in producing states that cannot be effectively simulated on a classical computer.
  arXiv  Detail & Related papers  (2022-03-31T18:00:01Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Quantum belief function [4.286327408435937]
  We encode the basic belief assignment (BBA) into quantum states, which makes each qubit correspond to control an element. We simulate our quantum version of BBA on Qiskit platform, which ensures the computation of our algorithm experimentally.
  arXiv  Detail & Related papers  (2021-07-08T15:57:32Z)
• 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)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)

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.