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
- 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) - Classically Simulating Quantum Supremacy IQP Circuits trough a Random
Graph Approach [0.0]
A good candidate for demonstrating quantum supremacy with random circuit sampling is to use emphIQP circuits.
We introduce improved techniques for classically simulating random IQP circuits.
We estimate that 70-qubit circuits are within reach for a large computing cluster.
arXiv Detail & Related papers (2022-12-16T17:38:42Z) - 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 circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
We present a technique that pinpoints the sections of a quantum circuit that affect the circuit output the most.
We demonstrate the practicality and efficacy of the proposed technique by applying it to example algorithmic circuits implemented on IBM quantum machines.
arXiv Detail & Related papers (2022-04-12T19:39:31Z) - 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) - Reducing the Depth of Linear Reversible Quantum Circuits [0.0]
In quantum computing the decoherence time of the qubits determines the computation time available.
We propose a practical formulation of a divide and conquer algorithm that produces quantum circuits that are twice as shallow as those produced by existing algorithms.
Overall, we manage to consistently reduce the total depth of a class of reversible functions, with up to 92% savings in an ancilla-free case and up to 99% when ancillary qubits are available.
arXiv Detail & Related papers (2022-01-17T12:36:32Z) - 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.