An unconditional distribution learning advantage with shallow quantum circuits

• URL: http://arxiv.org/abs/2411.15548v1
• Date: Sat, 23 Nov 2024 13:03:22 GMT
• Title: An unconditional distribution learning advantage with shallow quantum circuits
• Authors: N. Pirnay, S. Jerbi, J. -P. Seifert, J. Eisert,
• Abstract summary: We prove an unconditional quantum advantage in the probably approximately correct (PAC) distribution learning framework with shallow quantum circuit hypotheses. We identify a meaningful generative distribution learning problem where constant-depth quantum circuits using one and two qubit gates (QNC0) are superior compared to constant-depth bounded fan-in classical circuits (NC0) as a choice for hypothesis classes.
• Score: 0.0
• License:
• Abstract: One of the core challenges of research in quantum computing is concerned with the question whether quantum advantages can be found for near-term quantum circuits that have implications for practical applications. Motivated by this mindset, in this work, we prove an unconditional quantum advantage in the probably approximately correct (PAC) distribution learning framework with shallow quantum circuit hypotheses. We identify a meaningful generative distribution learning problem where constant-depth quantum circuits using one and two qubit gates (QNC^0) are superior compared to constant-depth bounded fan-in classical circuits (NC^0) as a choice for hypothesis classes. We hence prove a PAC distribution learning separation for shallow quantum circuits over shallow classical circuits. We do so by building on recent results by Bene Watts and Parham on unconditional quantum advantages for sampling tasks with shallow circuits, which we technically uplift to a hyperplane learning problem, identifying non-local correlations as the origin of the quantum advantage.

Related papers

• A circuit-generated quantum subspace algorithm for the variational quantum eigensolver [0.0]
  We propose combining quantum subspace techniques with the variational quantum eigensolver (VQE) In our approach, the parameterized quantum circuit is divided into a series of smaller subcircuits. The sequential application of these subcircuits to an initial state generates a set of wavefunctions that we use as a quantum subspace to obtain high-accuracy groundstate energies.
  arXiv  Detail & Related papers  (2024-04-09T18:00:01Z)
• Quantum Advantage: A Single Qubit's Experimental Edge in Classical Data Storage [5.669806907215807]
  We implement an experiment on a photonic quantum processor establishing efficacy of the elementary quantum system in classical information storage. Our work paves the way for immediate applications in near-term quantum technologies.
  arXiv  Detail & Related papers  (2024-03-05T05:09:32Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Instantaneous nonlocal quantum computation and circuit depth reduction [7.148511452018054]
  Two-party quantum computation is a computation process with bipartite input and output, in which there are initial shared entanglement. In the first part, we show that a particular simplified subprocedure, known as a garden-hose gadget, cannot significantly reduce the entanglement cost. In the second part, we show that any unitary circuit consisting of layers of Clifford gates and T gates can be implemented using a circuit with measurements of depth proportional to the T-depth of the original circuit.
  arXiv  Detail & Related papers  (2023-06-15T17:57:50Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Fundamental limitations on optimization in variational quantum algorithms [7.165356904023871]
  A leading paradigm to establish such near-term quantum applications is variational quantum algorithms (VQAs) We prove that for a broad class of such random circuits, the variation range of the cost function vanishes exponentially in the number of qubits with a high probability. This result can unify the restrictions on gradient-based and gradient-free optimizations in a natural manner and reveal extra harsh constraints on the training landscapes of VQAs.
  arXiv  Detail & Related papers  (2022-05-10T17:14:57Z)
• Locating quantum critical points with shallow quantum circuits [0.0]
  We propose an approach based on variational quantum eigensolver(VQE), dubbed as Delta-VQE, for locating the quantum critical point. The signature of a critical point as a minimal point can be sharper while using shallower quantum circuits.
  arXiv  Detail & Related papers  (2022-03-26T09:35:57Z)
• Gaussian initializations help deep variational quantum circuits escape from the barren plateau [87.04438831673063]
  Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years. However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number. This result leads to a general belief that deep quantum circuits will not be feasible for practical tasks.
  arXiv  Detail & Related papers  (2022-03-17T15:06:40Z)
• 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)
• Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
  We show that the advantage of quantum kernels is vanished for large size datasets, few number of measurements, and large system noise. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
  arXiv  Detail & Related papers  (2021-03-31T02:41:36Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

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.