On the moments of random quantum circuits and robust quantum complexity
- URL: http://arxiv.org/abs/2303.16944v2
- Date: Fri, 2 Jun 2023 00:54:58 GMT
- Title: On the moments of random quantum circuits and robust quantum complexity
- Authors: Jonas Haferkamp
- Abstract summary: We prove new lower bounds on the growth of robust quantum circuit complexity.
We show two bounds for random quantum circuits with local gates drawn from a subgroup of $SU(4)$.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove new lower bounds on the growth of robust quantum circuit complexity
-- the minimal number of gates $C_{\delta}(U)$ to approximate a unitary $U$ up
to an error of $\delta$ in operator norm distance. More precisely we show two
bounds for random quantum circuits with local gates drawn from a subgroup of
$SU(4)$. First, for $\delta=\Theta(2^{-n})$, we prove a linear growth rate:
$C_{\delta}\geq d/\mathrm{poly}(n)$ for random quantum circuits on $n$ qubits
with $d\leq 2^{n/2}$ gates. Second, for $ \delta=\Omega(1)$, we prove a
square-root growth of complexity: $C_{\delta}\geq \sqrt{d}/\mathrm{poly}(n)$
for all $d\leq 2^{n/2}$. Finally, we provide a simple conjecture regarding the
Fourier support of randomly drawn Boolean functions that would imply linear
growth for constant $\delta$. While these results follow from bounds on the
moments of random quantum circuits, we do not make use of existing results on
the generation of unitary $t$-designs. Instead, we bound the moments of an
auxiliary random walk on the diagonal unitaries acting on phase states. In
particular, our proof is comparably short and self-contained.
Related papers
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$.
As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
arXiv Detail & Related papers (2024-10-26T06:21:42Z) - Incompressibility and spectral gaps of random circuits [2.359282907257055]
reversible and quantum circuits form random walks on the alternating group $mathrmAlt (2n)$ and unitary group $mathrmSU (2n)$, respectively.
We prove that the gap for random reversible circuits is $Omega(n-3)$ for all $tgeq 1$, and the gap for random quantum circuits is $Omega(n-3)$ for $t leq Theta(2n/2)$.
arXiv Detail & Related papers (2024-06-11T17:23:16Z) - Unitary k-designs from random number-conserving quantum circuits [0.0]
Local random circuits scramble efficiently and accordingly have a range of applications in quantum information and quantum dynamics.
We show that finite moments cannot distinguish the ensemble that local random circuits generate from the Haar ensemble on the entire group of number-conserving unitaries.
arXiv Detail & Related papers (2023-06-01T18:00:00Z) - 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) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
We study quantum Ordered Binary Decision Diagrams($OBDD$) model.
We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables.
We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
arXiv Detail & Related papers (2022-04-22T12:37:56Z) - Optimal (controlled) quantum state preparation and improved unitary
synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
Controlled quantum state preparation (CQSP) aims to provide the transformation of $|irangle |0nrangle to |irangle |psi_irangle $ for all $iin 0,1k$ for the given $n$-qubit states.
We construct a quantum circuit for implementing CQSP, with depth $Oleft(n+k+frac2n+kn+k+mright)$ and size $Oleft(2n+kright)$
arXiv Detail & Related papers (2022-02-23T04:19:57Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.
For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially.
If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard.
We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
arXiv Detail & Related papers (2021-02-03T09:20:32Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - Epsilon-nets, unitary designs and random quantum circuits [0.11719282046304676]
Epsilon-nets and approximate unitary $t$-designs are notions of unitary operations relevant for numerous applications in quantum information and quantum computing.
We prove that for a fixed $d$ of the space, unitaries constituting $delta$-approx $t$-expanders form $epsilon$-nets for $tsimeqfracd5/2epsilon$ and $delta=left(fracepsilon3/2dright)d2$.
We show that approximate tdesigns can be generated
arXiv Detail & Related papers (2020-07-21T15:16:28Z)
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.