Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA simple method for sampling random Clifford operators
126
0
0.0
(
0
)
Authors
Ewout van den Berg
Ask ChatGPT about the research
No Arabic 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}(nlog 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.
rate research
Read More
Reconstructing continuous signals from a small number of discrete samples is a fundamental problem across science and engineering. In practice, we are often interested in signals with simple Fourier structure, such as bandlimited, multiband, and Fourier sparse signals. More broadly, any prior knowledge about a signals Fourier power spectrum can constrain its complexity. Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct. We formalize this intuition by showing that, roughly, a continuous signal from a given class can be approximately reconstructed using a number of samples proportional to the *statistical dimension* of the allowed power spectrum of that class. Further, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction. Surprisingly, we also show that, up to logarithmic factors, a universal non-uniform sampling strategy can achieve this optimal complexity for *any class of signals*. We present a simple and efficient algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art. At the same time, it gives the first computationally and sample efficient solution to a broad range of problems, including multiband signal reconstruction and kriging and Gaussian process regression tasks in one dimension. Our work is based on a novel connection between randomized linear algebra and signal reconstruction with constrained Fourier structure. We extend tools based on statistical leverage score sampling and column-based matrix reconstruction to the approximation of continuous linear operators that arise in signal reconstruction. We believe that these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.
Generation of deviates from random graph models with non-trivial edge dependence is an increasingly important problem. Here, we introduce a method which allows perfect sampling from random graph models in exponential family form (exponential family random graph models), using a variant of Coupling From The Past. We illustrate the use of the method via an application to the Markov graphs, a family that has been the subject of considerable research. We also show how the method can be applied to a variant of the biased net models, which are not exponentially parameterized.
Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that approximating the output probabilities of random quantum circuits to within $exp(-Omega(mlog m))$ additive error is hard for any classical computer, where $m$ is the number of gates in the quantum computation. More precisely, we show that the above problem is $#mathsf{P}$-hard under $mathsf{BPP}^{mathsf{NP}}$ reduction. In the recent experiments, the quantum circuit has $n$-qubits and the architecture is a two-dimensional grid of size $sqrt{n}timessqrt{n}$. Indeed for constant depth circuits approximating the output probabilities to within $2^{-Omega(nlog{n})}$ is hard. For circuits of depth $log{n}$ or $sqrt{n}$ for which the anti-concentration property holds, approximating the output probabilities to within $2^{-Omega(nlog^2{n})}$ and $2^{-Omega(n^{3/2}log n)}$ is hard respectively. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturis lemma, and Rakhmanovs result.
We show that low-depth random quantum circuits can be efficiently simulated by a quantum teleportation-inspired algorithm. By using logical qubits to redirect and teleport the quantum information in quantum circuits, the original circuits can be renormalized to new circuits with a smaller number of logical qubits. We demonstrate the algorithm to simulate several random quantum circuits, including 1D-chain 1000-qubit 42-depth, 2D-grid 125*8-qubit 42-depth and 2D-Bristlecone 72-qubit 32-depth circuits. Our results present a memory-efficient method with a clear physical picture to simulate low-depth random quantum circuits.
Single photon detectors are important for a wide range of applications each with their own specific requirements, which makes necessary the precise characterization of detectors. Here, we present a simple and accurate methodology of characterizing dark count rate, detection efficiency, and after-pulsing in single photon detectors purely based on their counting statistics. We demonstrate our new method on a custom-made, free-running single photon detector based on an InGaAs based avalanche photo diode (APD), though the methodology presented here is applicable for any type of single photon detector.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
