Quantum Circuit Completeness: Extensions and Simplifications

• URL: http://arxiv.org/abs/2303.03117v3
• Date: Fri, 1 Dec 2023 08:59:45 GMT
• Title: Quantum Circuit Completeness: Extensions and Simplifications
• Authors: Alexandre Cl\'ement, No\'e Delorme, Simon Perdrix, Renaud Vilmart
• Abstract summary: 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.
• Score: 44.99833362998488
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Although quantum circuits have been ubiquitous for decades in quantum computing, the first complete equational theory for quantum circuits has only recently been introduced. Completeness guarantees that any true equation on quantum circuits can be derived from the equational theory. We improve this completeness result in two ways: (i) We simplify the equational theory by proving that several rules can be derived from the remaining ones. In particular, two out of the three most intricate rules are removed, the third one being slightly simplified. (ii) The complete equational theory can be extended to quantum circuits with ancillae or qubit discarding, to represent respectively quantum computations using an additional workspace, and hybrid quantum computations. We show that the remaining intricate rule can be greatly simplified in these more expressive settings, leading to equational theories where all equations act on a bounded number of qubits. The development of simple and complete equational theories for expressive quantum circuit models opens new avenues for reasoning about quantum circuits. It provides strong formal foundations for various compiling tasks such as circuit optimisation, hardware constraint satisfaction and verification.

Related papers

• Exponential separation in quantum query complexity of the quantum switch with respect to simulations with standard quantum circuits [1.151731504874944]
  We prove that the action of the quantum switch on two $n$-qubit quantum channels cannot be simulated deterministically. This demonstrates an exponential separation in quantum query complexity of indefinite causal order compared to standard quantum circuits.
  arXiv  Detail & Related papers  (2024-09-27T03:18:28Z)
• 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)
• Minimal Equational Theories for Quantum Circuits [44.99833362998488]
  We show that any true equation on quantum circuits can be derived from simple rules. One of our main contributions is to prove the minimality of the equational theory.
  arXiv  Detail & Related papers  (2023-11-13T17:11:25Z)
• A Complete Equational Theory for Quantum Circuits [58.720142291102135]
  We introduce the first complete equational theory for quantum circuits. Two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations.
  arXiv  Detail & Related papers  (2022-06-21T17:56:31Z)
• Gaussian initializations help deep variational quantum circuits escape from the barren plateau [87.04438831673063]
  Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years. However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number. This result leads to a general belief that deep quantum circuits will not be feasible for practical tasks.
  arXiv  Detail & Related papers  (2022-03-17T15:06:40Z)
• Quantum Circuits in Additive Hilbert Space [0.0]
  We show how conventional circuits can be expressed in the additive space and how they can be recovered. In particular in our formalism we are able to synthesize high-level multi-controlled primitives from low-level circuit decompositions. Our formulation also accepts a circuit-like diagrammatic representation and proposes a novel and simple interpretation of quantum computation.
  arXiv  Detail & Related papers  (2021-11-01T19:05:41Z)
• 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)
• Equivalence Checking of Dynamic Quantum Circuits [7.835264621634824]
  State-of-the-art quantum devices still contain only a very limited number of qubits. One possible way to execute more realistic algorithms in near-term quantum devices is to employ dynamic quantum circuits. This technique can help to significantly reduce the resources required to achieve a given accuracy of a quantum algorithm.
  arXiv  Detail & Related papers  (2021-06-03T08:03:22Z)

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.