More Like this

1. Random Quantum Circuits Transform Local Noise into Global White Noise

   https://doi.org/10.1007/s00220-024-04958-z  

   Dalzell, Alexander M. ; Hunter-Jones, Nicholas ; Brandão, Fernando G. S. L. ( March 2024 , Communications in Mathematical Physics)

   We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gate-level error with probability close to one. We model noise by adding a pair of weak, unital, single-qubit noise channels after each two-qubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the corresponding noiseless output distribution$$p_{\text {ideal}}$$$p_{\text{ideal}}$shrink exponentially with the expected number of gate-level errors. Specifically, the linear cross-entropy benchmarkFthat measures this correlation behaves as$$F=\text {exp}(-2s\epsilon \pm O(s\epsilon ^2))$$$F=\text{exp}(-2sϵ\pm O\left(s{ϵ}^2\right))$, where$$\epsilon $$$ϵ$is the probability of error per circuit location andsis the number of two-qubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the uniform distribution$$p_{\text {unif}}$$$p_{\text{unif}}$decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as$$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1-F)p_{\text {unif}}$$$p_{\text{noisy}}\approx F{p}_{\text{ideal}}+(1-F)p_{\text{unif}}$. In other words, although at least one local error occurs with probability$$1-F$$$1-F$, the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by$$O(F\epsilon \sqrt{s})$$$O\left(Fϵ\sqrt{s}\right)$. Thus, the “white-noise approximation” is meaningful when$$\epsilon \sqrt{s} \ll 1$$$ϵ\sqrt{s}\ll 1$, a quadratically weaker condition than the$$\epsilon s\ll 1$$$ϵs\ll 1$requirement to maintain high fidelity. The bound applies if the circuit size satisfies$$s \ge \Omega (n\log (n))$$$s\ge \Omega (nlog(n\left)\right)$, which corresponds to onlylogarithmic depthcircuits, and if, additionally, the inverse error rate satisfies$$\epsilon ^{-1} \ge {\tilde{\Omega }}(n)$$${ϵ}^{-1}\ge \tilde{\Omega }\left(n\right)$, which is needed to ensure errors are scrambled faster thanFdecays. The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; for example, it was an underlying assumption in complexity-theoretic arguments that noisy random quantum circuits cannot be efficiently sampled classically, even when the fidelity is low. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds.

    

   more » « less
2. Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity

   https://doi.org/10.1007/s00453-023-01102-6  

   Akmal, Shyan ; Chen, Lijie ; Jin, Ce ; Raj, Malvika ; Williams, Ryan ( February 2023 , Algorithmica)

   In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include:

   Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time$$\tilde{O}(n)$$$\tilde{O}\left(n\right)$. Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in$$\tilde{O}(n^{1.5})$$$\tilde{O}\left(n^{1.5}\right)$time (that is, there is a proof system with proofs of length$$\tilde{O}(n^{1.5})$$$\tilde{O}\left(n^{1.5}\right)$and a deterministic verifier running in$$\tilde{O}(n^{1.5})$$$\tilde{O}\left(n^{1.5}\right)$time).

   Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time$${\tilde{O}}(n^{\lceil k/2\rceil })$$$\tilde{O}\left(n^{\lceil k/2\rceil }\right)$(where$$k\ge 3$$$k\ge 3$). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time$${\tilde{O}}(m)$$$\tilde{O}\left(m\right)$. Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk.

   Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time$$\tilde{O}(n^2)$$$\tilde{O}\left(n^2\right)$. Note this is optimal, as the matrix can have$$\Omega (n^2)$$$\Omega \left(n^2\right)$nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an$$\tilde{O}(n^{2.94})$$$\tilde{O}\left(n^{2.94}\right)$nondeterministic time algorithm.

   Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time$$2^{n/2 - n/O(k)}$$$2^{n/2-n/O\left(k\right)}$. We also observe an algebrization barrier for the previous$$2^{n/2}\cdot \textrm{poly}(n)$$$2^{n/2}·\text{poly}\left(n\right)$-time Merlin–Arthur protocol of R. Williams [CCC’16] for$$\#$$$\#$SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running in$$2^{n/2}/n^{\omega (1)}$$$2^{n/2}/n^{\omega \left(1\right)}$time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.

   Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time$$2^{4n/5}\cdot \textrm{poly}(n)$$$2^{4n/5}·\text{poly}\left(n\right)$. Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in$$2^{2n/3}\cdot \textrm{poly}(n)$$$2^{2n/3}·\text{poly}\left(n\right)$time.

   Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time$$2^{n/3}\cdot \textrm{poly}(n)$$$2^{n/3}·\text{poly}\left(n\right)$, improving on the previous best protocol by Nederlof [IPL 2017] which took$$2^{0.49991n}\cdot \textrm{poly}(n)$$$2^{0.49991n}·\text{poly}\left(n\right)$time.

    

   more » « less
3. The stable exotic Cuntz algebras are higher-rank graph algebras

   https://doi.org/10.1090/bproc/180  

   Boersema, Jeffrey ; Browne, Sarah ; Gillaspy, Elizabeth ( March 2024 , Proceedings of the American Mathematical Society, Series B)

   For each odd integer$n \geq 3$, we construct a rank-3 graph$\Lambda _n$with involution$\gamma _n$whose real$C^*$-algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)$is stably isomorphic to the exotic Cuntz algebra$\mathcal E_n$. This construction is optimal, as we prove that a rank-2 graph with involution$(\Lambda ,\gamma )$can never satisfy$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n$, and Boersema reached the same conclusion for rank-1 graphs (directed graphs) in [Münster J. Math.10(2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank-1 graph with involution$(\Lambda , \gamma )$whose real$C^*$-algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )$is stably isomorphic to the suspension$S \mathbb {R}$. In the Appendix, we show that the$i$-fold suspension$S^i \mathbb {R}$is stably isomorphic to a graph algebra iff$-2 \leq i \leq 1$.

    

   more » « less
4. The Brown measure of the free multiplicative Brownian motion

   https://doi.org/10.1007/s00440-022-01142-z  

   Driver, Bruce K. ; Hall, Brian ; Kemp, Todd ( October 2022 , Probability Theory and Related Fields)

   The free multiplicative Brownian motion$$b_{t}$$$b_t$is the large-Nlimit of the Brownian motion on$$\mathsf {GL}(N;\mathbb {C}),$$$\mathrm{GL}(N;C),$in the sense of$$*$$$\ast$-distributions. The natural candidate for the large-Nlimit of the empirical distribution of eigenvalues is thus the Brown measure of$$b_{t}$$$b_t$. In previous work, the second and third authors showed that this Brown measure is supported in the closure of a region$$\Sigma _{t}$$${\Sigma }_t$that appeared in the work of Biane. In the present paper, we compute the Brown measure completely. It has a continuous density$$W_{t}$$$W_t$on$$\overline{\Sigma }_{t},$$${\overline{\Sigma }}_t,$which is strictly positive and real analytic on$$\Sigma _{t}$$${\Sigma }_t$. This density has a simple form in polar coordinates:$$\begin{aligned} W_{t}(r,\theta )=\frac{1}{r^{2}}w_{t}(\theta ), \end{aligned}$$$\begin{array}{c}{W}_t(r,\theta )=\frac{1}{r^2}{w}_t\left(\theta \right),\end{array}$where$$w_{t}$$$w_t$is an analytic function determined by the geometry of the region$$\Sigma _{t}$$${\Sigma }_t$. We show also that the spectral measure of free unitary Brownian motion$$u_{t}$$$u_t$is a “shadow” of the Brown measure of$$b_{t}$$$b_t$, precisely mirroring the relationship between the circular and semicircular laws. We develop several new methods, based on stochastic differential equations and PDE, to prove these results.

    

   more » « less
5. Finding solutions with distinct variables to systems of linear equations over $$\mathbb {F}_p$$

   https://doi.org/10.1007/s00208-022-02391-y  

   Sauermann, Lisa ( April 2022 , Mathematische Annalen)

   Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$$a_{j,1}{x}_1+\cdots +a_{j,k}{x}_k=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$with coefficients$$a_{j,i}\in \mathbb {F}_p$$$a_{j,i}\in F_p$. Suppose that$$k\ge 3m$$$k\ge 3m$, that$$a_{j,1}+\dots +a_{j,k}=0$$$a_{j,1}+\cdots +a_{j,k}=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$and that every$$m\times m$$$m\times m$minor of the$$m\times k$$$m\times k$matrix$$(a_{j,i})_{j,i}$$${\left(a_{j,i}\right)}_{j,i}$is non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$$A\subseteq F_p^n$of size$$|A|> C\cdot \Gamma ^n$$$\left|A\right|>C·{\Gamma }^n$contains a solution$$(x_1,\dots ,x_k)\in A^k$$$(x_1,\cdots ,x_k)\in A^k$to the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$$x_1,\cdots ,x_k\in A$are all distinct. Here,Cand$$\Gamma $$$\Gamma$are constants only depending onp,mandksuch that$$\Gamma $\Gamma <p$. The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$$x_1,\cdots ,x_k$in the solution$$(x_1,\dots ,x_k)\in A^k$$$(x_1,\cdots ,x_k)\in A^k$to be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$$x_1,\cdots ,x_k$are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments.

    

   more » « less