Computational power of one- and two-dimensional dual-unitary quantum circuits

• URL: http://arxiv.org/abs/2103.09211v2
• Date: Tue, 18 Jan 2022 16:36:20 GMT
• Title: Computational power of one- and two-dimensional dual-unitary quantum circuits
• Authors: Ryotaro Suzuki, Kosuke Mitarai, Keisuke Fujii
• Abstract summary: Quantum circuits that are classically simulatable tell us when quantum computation becomes less powerful than or equivalent to classical computation. We make use of dual-unitary quantum circuits (DUQCs), which have been recently investigated as exactly solvable models of non-equilibrium physics.
• Score: 0.6946929968559495
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum circuits that are classically simulatable tell us when quantum computation becomes less powerful than or equivalent to classical computation. Such classically simulatable circuits are of importance because they illustrate what makes universal quantum computation different from classical computers. In this work, we propose a novel family of classically simulatable circuits by making use of dual-unitary quantum circuits (DUQCs), which have been recently investigated as exactly solvable models of non-equilibrium physics, and we characterize their computational power. Specifically, we investigate the computational complexity of the problem of calculating local expectation values and the sampling problem of one-dimensional DUQCs, and we generalize them to two spatial dimensions. We reveal that a local expectation value of a DUQC is classically simulatable at an early time, which is linear in a system length. In contrast, in a late time, they can perform universal quantum computation, and the problem becomes a BQP-complete problem. Moreover, classical simulation of sampling from a DUQC turns out to be hard.

Related papers

• An Efficient Classical Algorithm for Simulating Short Time 2D Quantum Dynamics [2.891413712995642]
  We introduce an efficient classical algorithm for simulating short-time dynamics in 2D quantum systems. Our results reveal the inherent simplicity in the complexity of short-time 2D quantum dynamics. This work advances our understanding of the boundary between classical and quantum computation.
  arXiv  Detail & Related papers  (2024-09-06T09:59:12Z)
• 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)
• The computational power of random quantum circuits in arbitrary geometries [1.5683842542033573]
  Recent upgrades to Quantinuum's H2 quantum computer enable it to operate on up to $56$ qubits with arbitrary connectivity and $99.843(5)%$ two-qubit gate fidelity. We present data from random circuit sampling in highly connected geometries, doing so at unprecedented fidelities and a scale that appears to be beyond the capabilities of state-of-the-art classical algorithms.
  arXiv  Detail & Related papers  (2024-06-04T17:20:30Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• Exponential quantum speedup in simulating coupled classical oscillators [1.9398245011675082]
  We present a quantum algorithm for the classical dynamics of $2n$ coupled oscillators. Our approach leverages a mapping between the Schr"odinger equation and Newton's equation for harmonic potentials. We show that our approach solves a potentially practical application with an exponential speedup over classical computers.
  arXiv  Detail & Related papers  (2023-03-23T03:24:03Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• 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)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Fault-tolerant quantum speedup from constant depth quantum circuits [0.0]
  We show that there is no classical algorithm which can sample according to its output distribution in $poly(n)$ time. We present two constructions, each taking $poly(n)$ physical qubits, some of which are prepared in noisy magic states.
  arXiv  Detail & Related papers  (2020-05-23T13:53:27Z)
• Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices [0.0]
  We introduce a quantum solver of contracted eigenvalue equations, the quantum analogue of classical methods for the energies. We demonstrate the algorithm though computations on both a quantum simulator and two IBM quantum processing units.
  arXiv  Detail & Related papers  (2020-04-23T18:35: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.