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

• 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)
• 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 Circuit Completeness: Extensions and Simplifications [44.99833362998488]
  The first complete equational theory for quantum circuits has only recently been introduced. We simplify the equational theory by proving that several rules can be derived from the remaining ones. The complete equational theory can be extended to quantum circuits with ancillae or qubit discarding.
  arXiv  Detail & Related papers  (2023-03-06T13:31:27Z)
• 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)
• 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.