Short Proofs of Linear Growth of Quantum Circuit Complexity
- URL: http://arxiv.org/abs/2205.05668v1
- Date: Wed, 11 May 2022 17:53:57 GMT
- Title: Short Proofs of Linear Growth of Quantum Circuit Complexity
- Authors: Zhi Li
- Abstract summary: 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.
- Score: 3.8340125020400366
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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. In this article, we provide two short proofs of this fact. We
also discuss a discrete version of quantum circuit complexity growth.
Related papers
- 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) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - Diamond-shaped quantum circuit for real-time quantum dynamics in one
dimension [0.0]
We show that quantum many-body states can be universally represented using a quantum circuit comprising multi-qubit gates.
We also evaluate the efficiency of a quantum circuit constructed with two-qubit gates in quench dynamics for the transverse-field Ising model.
Our results reveal that a diamond-shaped quantum circuit, designed to approximate the multi-qubit gate-based quantum circuit, remarkably excels in accurately representing the long-time dynamics of the system.
arXiv Detail & Related papers (2023-11-10T07:07:54Z) - A vertical gate-defined double quantum dot in a strained germanium
double quantum well [48.7576911714538]
Gate-defined quantum dots in silicon-germanium heterostructures have become a compelling platform for quantum computation and simulation.
We demonstrate the operation of a gate-defined vertical double quantum dot in a strained germanium double quantum well.
We discuss challenges and opportunities and outline potential applications in quantum computing and quantum simulation.
arXiv Detail & Related papers (2023-05-23T13:42:36Z) - 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) - 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) - 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) - Linear growth of quantum circuit complexity [0.6299766708197883]
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.
arXiv Detail & Related papers (2021-06-09T18:01:57Z) - Entangling power and quantum circuit complexity [0.0]
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.
arXiv Detail & Related papers (2021-04-07T18:01:06Z) - 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.