Entangling power and quantum circuit complexity
- URL: http://arxiv.org/abs/2104.03332v3
- Date: Fri, 4 Jun 2021 05:48:26 GMT
- Title: Entangling power and quantum circuit complexity
- Authors: J. Eisert
- Abstract summary: We discuss a simple such relationship when both the entanglement of a state and the cost of a unitary take small values.
This bound implies that if entanglement entropies grow linearly in time, so does the cost.
In the context of quantum simulation, it allows to compare digital and analog quantum simulators.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Notions of circuit complexity and cost play a key role in quantum computing
and simulation where they capture the (weighted) minimal number of gates that
is required to implement a unitary. Similar notions also become increasingly
prominent in high energy physics in the study of holography. While notions of
entanglement have in general little implications for the quantum circuit
complexity and the cost of a unitary, in this note, we discuss a simple such
relationship when both the entanglement of a state and the cost of a unitary
take small values, building on ideas on how values of entangling power of
quantum gates add up. This bound implies that if entanglement entropies grow
linearly in time, so does the cost. The implications are two-fold: It provides
insights into complexity growth for short times. In the context of quantum
simulation, it allows to compare digital and analog quantum simulators. The
main technical contribution is a continuous-variable small incremental
entangling bound.
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) - Character Complexity: A Novel Measure for Quantum Circuit Analysis [0.0]
This paper introduces Character Complexity, a novel measure that bridges Group-theoretic concepts with practical quantum computing concerns.
I prove several key properties of character complexity and establish a surprising connection to the classical simulability of quantum circuits.
I present innovative visualization methods for character complexity, providing intuitive insights into the structure of quantum circuits.
arXiv Detail & Related papers (2024-08-19T01:58:54Z) - 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) - Quantum complexity phase transitions in monitored random circuits [0.29998889086656577]
We study the dynamics of the quantum state complexity in monitored random circuits.
We find that the evolution of the exact quantum state complexity undergoes a phase transition when changing the measurement rate.
arXiv Detail & Related papers (2023-05-24T18:00:11Z) - 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) - 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) - 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) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates.
We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions.
The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
arXiv Detail & Related papers (2021-08-06T19:38:03Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems.
We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z) - 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)
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.