Related papers: A simple method for sampling random Clifford operators

A simple method for sampling random Clifford operators

URL: http://arxiv.org/abs/2008.06011v4
Date: Tue, 17 Aug 2021 11:58:02 GMT
Title: A simple method for sampling random Clifford operators
Authors: Ewout van den Berg
Abstract summary: We describe a simple algorithm for sampling $n$-qubit Clifford operators uniformly at random. The algorithm outputs the Clifford operators in the form of quantum circuits with at most $5n + 2n2$ elementary gates and a maximum depth of $mathcalO(nlog n)$ on fully connected topologies.
Score: 1.0587959762260986
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We describe a simple algorithm for sampling $n$-qubit Clifford operators uniformly at random. The algorithm outputs the Clifford operators in the form of quantum circuits with at most $5n + 2n^2$ elementary gates and a maximum depth of $\mathcal{O}(n\log n)$ on fully connected topologies. The circuit can be output in a streaming fashion as the algorithm proceeds, and different parts of the circuit can be generated in parallel. The algorithm has an $\mathcal{O}(n^2)$ time complexity, which matches the current state of the art. The main advantage of the proposed algorithm, however, lies in its simplicity and elementary derivation.

Related papers

A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
arXiv Detail & Related papers (2024-09-07T06:37:23Z)
Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
arXiv Detail & Related papers (2024-08-10T04:26:19Z)
A simple asymptotically optimal Clifford circuit compilation algorithm [0.0]
We present an algorithm that decomposes any $n$-qubit Clifford operator into a circuit consisting of three subcircuits. As with other derivationally optimal Clifford compilation algorithms, the resulting circuit contains $O(n2/log n)$ two-qubit gates.
arXiv Detail & Related papers (2023-10-16T23:27:59Z)
Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
We describe an algorithm with quasipolynomial runtime $nO(logn)$ that samples from the output distribution of a peaked constant-depth circuit. Our algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error.
arXiv Detail & Related papers (2023-09-15T14:01:13Z)
Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
We show that a na"ive partitioning and low-order splitting formula can yield, through our divide and conquer formalism, superior scaling to qubitization for large $Lambda$. We also give new algorithmic and circuit level techniques for gate optimization including a new way of implementing a group of multi-controlled-X gates.
arXiv Detail & Related papers (2023-06-19T23:20:30Z)
On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
arXiv Detail & Related papers (2023-01-11T09:12:28Z)
Classically Simulating Quantum Supremacy IQP Circuits trough a Random Graph Approach [0.0]
A good candidate for demonstrating quantum supremacy with random circuit sampling is to use emphIQP circuits. We introduce improved techniques for classically simulating random IQP circuits. We estimate that 70-qubit circuits are within reach for a large computing cluster.
arXiv Detail & Related papers (2022-12-16T17:38:42Z)
A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z)
Eliminating Intermediate Measurements using Pseudorandom Generators [1.218340575383456]
We show that quantum algorithms of time $T$ and space $Sge log T$ can be simulated by quantum algorithms of time $T cdot mathrmpoly (S)$ and space $ O(Scdot log T)$ with unitary operations and without intermediate measurements.
arXiv Detail & Related papers (2021-06-22T15:47:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.