Learning shallow quantum circuits
- URL: http://arxiv.org/abs/2401.10095v1
- Date: Thu, 18 Jan 2024 16:05:00 GMT
- Title: Learning shallow quantum circuits
- Authors: Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag
Anshu, Zeph Landau, Jarrod R. McClean
- Abstract summary: We present an algorithm for learning the description of any unknown $n$-qubit shallow quantum circuit $U$.
We also provide a classical algorithm for learning the description of any unknown $n$-qubit state $lvert psi rangle$.
Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions.
- Score: 7.411898489476803
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Despite fundamental interests in learning quantum circuits, the existence of
a computationally efficient algorithm for learning shallow quantum circuits
remains an open question. Because shallow quantum circuits can generate
distributions that are classically hard to sample from, existing learning
algorithms do not apply. In this work, we present a polynomial-time classical
algorithm for learning the description of any unknown $n$-qubit shallow quantum
circuit $U$ (with arbitrary unknown architecture) within a small diamond
distance using single-qubit measurement data on the output states of $U$. We
also provide a polynomial-time classical algorithm for learning the description
of any unknown $n$-qubit state $\lvert \psi \rangle = U \lvert 0^n \rangle$
prepared by a shallow quantum circuit $U$ (on a 2D lattice) within a small
trace distance using single-qubit measurements on copies of $\lvert \psi
\rangle$. Our approach uses a quantum circuit representation based on local
inversions and a technique to combine these inversions. This circuit
representation yields an optimization landscape that can be efficiently
navigated and enables efficient learning of quantum circuits that are
classically hard to simulate.
Related papers
- Learning quantum states prepared by shallow circuits in polynomial time [1.127500169412367]
We learn a constant depth quantum circuit that prepares $vertpsirangle$ on a finite-dimensional lattice.
The algorithm extends to the case when the depth of $U$ is $mathrmpolylog(n)$, with a quasi-polynomial run-time.
As an application, we give an efficient algorithm to test whether an unknown quantum state on a lattice has low or high quantum circuit complexity.
arXiv Detail & Related papers (2024-10-31T04:12:49Z) - Learning shallow quantum circuits with many-qubit gates [1.879968161594709]
We present the first computationally-efficient algorithm for average-case learning of quantum circuits with many-qubit gates.
We show that the learned unitary can be efficiently synthesized in poly-logarithmic depth.
arXiv Detail & Related papers (2024-10-22T04:48:36Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods.
We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM)
The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
arXiv Detail & Related papers (2024-01-20T15:32:01Z) - 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) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits.
We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
arXiv Detail & Related papers (2022-01-27T13:16:30Z) - A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems.
We numerically demonstrate that the MNIST image dataset satisfies such conditions.
We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
arXiv Detail & Related papers (2021-07-19T23:41:03Z) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task.
Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate.
The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
arXiv Detail & Related papers (2021-06-06T13:15:25Z) - Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor
Network States Algorithm [0.0]
Algorithm is up to $2$ orders of magnitudes faster than Sch$ddottexto$dinger-Feynman algorithm.
We simulate larger random quantum circuits up to $104$ qubits, showing that this algorithm is an ideal tool to verify relatively shallow quantum circuits on near-term quantum computers.
arXiv Detail & Related papers (2020-11-05T02:20:56Z) - 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.