Linear growth of quantum circuit complexity
- URL: http://arxiv.org/abs/2106.05305v3
- Date: Wed, 22 Dec 2021 10:57:16 GMT
- Title: Linear growth of quantum circuit complexity
- Authors: Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert,
Nicole Yunger Halpern
- Abstract summary: We prove a conjecture by Brown and Susskind about how random quantum circuits' complexity increases.
Our proof is surprisingly short, given the established difficulty of lower-bounding the exact circuit complexity.
- Score: 0.6299766708197883
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantifying quantum states' complexity is a key problem in various subfields
of science, from quantum computing to black-hole physics. We prove a prominent
conjecture by Brown and Susskind about how random quantum circuits' complexity
increases. Consider constructing a unitary from Haar-random two-qubit quantum
gates. Implementing the unitary exactly requires a circuit of some minimal
number of gates - the unitary's exact circuit complexity. We prove that this
complexity grows linearly with the number of random gates, with unit
probability, until saturating after exponentially many random gates. Our proof
is surprisingly short, given the established difficulty of lower-bounding the
exact circuit complexity. Our strategy combines differential topology and
elementary algebraic geometry with an inductive construction of Clifford
circuits.
Related papers
- Learning marginals suffices! [14.322753787990036]
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.
arXiv Detail & Related papers (2023-03-15T21:09:29Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - A Complete Equational Theory for Quantum Circuits [58.720142291102135]
We introduce the first complete equational theory for quantum circuits.
Two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations.
arXiv Detail & Related papers (2022-06-21T17:56:31Z) - Estimating the randomness of quantum circuit ensembles up to 50 qubits [9.775777593425452]
We show that the ability of random circuits to approximate any random unitaries has consequences on their complexity, expressibility, and trainability.
Our work shows that large-scale tensor network simulations could provide important hints toward open problems in quantum information science.
arXiv Detail & Related papers (2022-05-19T23:43:15Z) - Short Proofs of Linear Growth of Quantum Circuit Complexity [3.8340125020400366]
The complexity of a quantum gate, defined as the minimal number of elementary gates to build it, is an important concept in quantum information and computation.
It is shown recently that the complexity of quantum gates built from random quantum circuits almost surely grows linearly with the number of building blocks.
arXiv Detail & Related papers (2022-05-11T17:53:57Z) - Escaping from the Barren Plateau via Gaussian Initializations in Deep Variational Quantum Circuits [63.83649593474856]
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 standpoint that deep quantum circuits would not be feasible for practical tasks.
arXiv Detail & Related papers (2022-03-17T15:06:40Z) - Transitions in Entanglement Complexity in Random Circuits [0.0]
We numerically show how a crossover from a simple pattern of entanglement to a universal, complex pattern can be driven by doping a random Clifford circuit with $T$ gates.
This work shows that quantum complexity and complex entanglement stem from the conjunction of entanglement and non-stabilizer resources, also known as magic.
arXiv Detail & Related papers (2022-02-05T22:30:24Z) - Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware.
We present an algorithm that compresses the Trotter steps into a single block of quantum gates.
This results in a fixed depth time evolution for certain classes of Hamiltonians.
arXiv Detail & Related papers (2021-08-06T19:38:01Z) - Sample Complexity of Learning Quantum Circuits [4.329298109272386]
We prove that physical quantum circuits are PAC learnable on a quantum computer via empirical risk minimization.
Our results provide a valuable guide for quantum machine learning in both theory and experiment.
arXiv Detail & Related papers (2021-07-19T18:00:04Z) - 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) - On estimating the entropy of shallow circuit outputs [49.1574468325115]
Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing.
We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
arXiv Detail & Related papers (2020-02-27T15:32:08Z)
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.