Learning marginals suffices!

• URL: http://arxiv.org/abs/2303.08938v2
• Date: Wed, 27 Sep 2023 12:20:19 GMT
• Title: Learning marginals suffices!
• Authors: Nengkun Yu, Tzu-Chieh Wei
• Abstract summary: We investigate the relationship between the sample complexity of learning a quantum state and the circuit complexity of the state. We show that learning its marginals for the quantum state with low circuit complexity suffices for state tomography.
• Score: 14.322753787990036
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Beyond computer science, quantum complexity theory can potentially revolutionize multiple branches of physics, ranging from quantum many-body systems to quantum field theory. In this paper, we investigate the relationship between the sample complexity of learning a quantum state and the circuit complexity of the state. The circuit complexity of a quantum state refers to the minimum depth of the quantum circuit necessary to implement it. We show that learning its marginals for the quantum state with low circuit complexity suffices for state tomography, thus breaking the exponential barrier of the sample complexity for quantum state tomography. Our proof is elementary and overcomes difficulties characterizing short-range entanglement by bridging quantum circuit complexity and ground states of gapped local Hamiltonians. Our result, for example, settles the quantum circuit complexity of the multi-qubit GHZ state exactly.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• 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)
• Complexity analysis of weakly noisy quantum states via quantum machine learning [1.203955415344484]
  We focus on the complexity of weakly noisy states, which we define as the size of the shortest quantum circuit required to prepare the noisy state. We propose a quantum machine learning (QML) algorithm that exploits the intrinsic-connection property of structured quantum neural networks.
  arXiv  Detail & Related papers  (2023-03-31T06:02:44Z)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit. We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
  arXiv  Detail & Related papers  (2023-03-02T18:08:08Z)
• Wasserstein Complexity of Quantum Circuits [10.79258896719392]
  Given a unitary transformation, what is the size of the smallest quantum circuit that implements it? This quantity, known as the quantum circuit complexity, is a fundamental property of quantum evolutions. We show that our new measure also provides a lower bound for the experimental cost of implementing quantum circuits.
  arXiv  Detail & Related papers  (2022-08-12T14:44:13Z)
• 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)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
  arXiv  Detail & Related papers  (2020-12-28T18:04:16Z)
• Quantum State Complexity in Computationally Tractable Quantum Circuits [0.0]
  We discuss a special class of numerically tractable quantum circuits, known as quantum automaton circuits. We show that automaton wave functions have high quantum state complexity. We present evidence of a linear growth of design complexity in local quantum circuits.
  arXiv  Detail & Related papers  (2020-09-11T16:25:11Z)
• Characterization of quantum states based on creation complexity [0.0]
  The creation complexity of a quantum state is the minimum number of elementary gates required to create it from a basic initial state. We show for an entirely general quantum state it is exponentially hard (requires a number of steps that scales exponentially with the number of qubits) to determine if the creation complexity is. We then show it is possible for a large class of quantum states with creation complexity to have common coefficient features such that given any candidate quantum state we can design an efficient coefficient sampling procedure to determine if it belongs to the class or not with arbitrarily high success probability.
  arXiv  Detail & Related papers  (2020-04-28T21:12:45Z)

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.