Unconditional quantum magic advantage in shallow circuit computation

• URL: http://arxiv.org/abs/2402.12246v2
• Date: Sat, 30 Nov 2024 14:46:53 GMT
• Title: Unconditional quantum magic advantage in shallow circuit computation
• Authors: Xingjian Zhang, Zhaokai Pan, Guoding Liu,
• Abstract summary: Quantum theory promises computational speed-ups over classical approaches. The Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of "magic" states. In this work, we demonstrate the first unconditional magic advantage.
• Score: 2.517043342442487
• License:
• Abstract: Quantum theory promises computational speed-ups over classical approaches. The celebrated Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of "magic" states -- the secret sauce to establish universal quantum computation. However, it is still questionable whether magic indeed brings the believed quantum advantage, ridding unproven complexity assumptions or black-box oracles. In this work, we demonstrate the first unconditional magic advantage: a separation between the power of generic constant-depth or shallow quantum circuits and magic-free counterparts. For this purpose, we link the shallow circuit computation with the strongest form of quantum nonlocality -- quantum pseudo-telepathy, where distant non-communicating observers generate perfectly synchronous statistics. We prove quantum magic is indispensable for such correlated statistics in a specific nonlocal game inspired by the linear binary constraint system. Then, we translate generating quantum pseudo-telepathy into computational tasks, where magic is necessary for a shallow circuit to meet the target. As a by-product, we provide an efficient algorithm to solve a general linear binary constraint system over the Pauli group, in contrast to the broad undecidability in constraint systems. We anticipate our results will enlighten the final establishment of the unconditional advantage of universal quantum computation.

Related papers

• Experimental Demonstration of Logical Magic State Distillation [62.77974948443222]
  We present the experimental realization of magic state distillation with logical qubits on a neutral-atom quantum computer. Our approach makes use of a dynamically reconfigurable architecture to encode and perform quantum operations on many logical qubits in parallel.
  arXiv  Detail & Related papers  (2024-12-19T18:38:46Z)
• Towards Entropic Constraints on Quantum Speedups [0.0]
  Some quantum algorithms have "quantum speedups": improved time complexity as compared with the best-known classical algorithms for solving the same tasks. Can we understand what fuels these speedups from an entropic perspective? Information theory gives us a multitude of metrics we might choose from to measure how fundamentally 'quantum' is the behavior of a quantum computer running an algorithm.
  arXiv  Detail & Related papers  (2024-11-05T19:00:04Z)
• The curse of random quantum data [62.24825255497622]
  We quantify the performances of quantum machine learning in the landscape of quantum data. We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits. Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
  arXiv  Detail & Related papers  (2024-08-19T12:18:07Z)
• Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
  We consider an approach to the question of describing a class of problems whose solution can be accelerated by a quantum computer. The unitary operation that transforms the initial quantum state into the desired one must be decomposable into a sequence of one- and two-qubit gates.
  arXiv  Detail & Related papers  (2024-03-25T15:47:35Z)
• Quantum Ruzsa Divergence to Quantify Magic [0.0]
  We investigate the behavior of quantum entropy under quantum convolution and its application in magic. We introduce a new quantum divergence based on quantum convolution, called the quantum Ruzsa divergence, to study the stabilizer structure of quantum states.
  arXiv  Detail & Related papers  (2024-01-25T18:43:24Z)
• 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)
• Complexity of quantum circuits via sensitivity, magic, and coherence [5.630280136865099]
  We study the complexity of quantum circuits using the notions of sensitivity, average sensitivity (also called influence), magic, and coherence. Our results are pivotal for understanding the role of sensitivity, magic, and coherence in quantum computation.
  arXiv  Detail & Related papers  (2022-04-26T03:15:09Z)
• 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)
• 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.