 NSFPAR ID:
 10374052
 Date Published:
 Journal Name:
 Symmetry
 Volume:
 14
 Issue:
 7
 ISSN:
 20738994
 Page Range / eLocation ID:
 1348
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Quantum lowdensity paritycheck (LDPC) codes are an important class of quantum error correcting codes. In such codes, each qubit only affects a constant number of syndrome bits, and each syndrome bit only relies on some constant number of qubits. Constructing quantum LDPC codes is challenging. It is an open problem to understand if there exist good quantum LDPC codes, i.e. with constant rate and relative distance. Furthermore, techniques to perform faulttolerant gates are poorly understood. We present a unified way to address these problems. Our main results are a) a bound on the distance, b) a bound on the code dimension and c) limitations on certain faulttolerant gates that can be applied to quantum LDPC codes. All three of these bounds are cast as a function of the graph separator of the connectivity graph representation of the quantum code. We find that unless the connectivity graph contains an expander, the code is severely limited. This implies a necessary, but not sufficient, condition to construct good codes. This is the first bound that studies the limitations of quantum LDPC codes that does not rely on locality. As an application, we present novel bounds on quantum LDPC codes associated with local graphs in D dimensional hyperbolic space.more » « less

Braverman, Mark (Ed.)For an abelian group H acting on the set [𝓁], an (H,𝓁)lift of a graph G₀ is a graph obtained by replacing each vertex by 𝓁 copies, and each edge by a matching corresponding to the action of an element of H. Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are nonexplicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019]. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(𝓁), constant degree d ≥ 3 and ε > 0, we construct explicit dregular expander graphs G obtained from an (H,𝓁)lift of a (suitable) base nvertex expander G₀ with the following parameters: ii) λ(G) ≤ 2√{d1} + ε, for any lift size 𝓁 ≤ 2^{n^{δ}} where δ = δ(d,ε), iii) λ(G) ≤ ε ⋅ d, for any lift size 𝓁 ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or iv) λ(G) ≤ Õ(√d), for lift size "exactly" 𝓁 = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasicyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depthfirst search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.more » « less

We present exact results that give insight into how interactions lead to transport and superconductivity in a flat band where the electrons have no kinetic energy. We obtain bounds for the optical spectral weight for flatband superconductors that lead to upper bounds for the superfluid stiffness and the twodimensional (2D)
${T}_{c}$ . We focus on onsite attraction$\leftU\right$ on the Lieb lattice with trivial flat bands and on the πflux model with topological flat bands. For trivial flat bands, the lowenergy optical spectral weight${\stackrel{\u0303}{D}}_{\text{low}}\le \stackrel{\u0303}{n}\leftU\right\mathrm{\Omega}/2$ with$\stackrel{\u0303}{n}=min\left(n,2n\right)$ , where n is the flatband density and Ω is the Marzari–Vanderbilt spread of the Wannier functions (WFs). We also obtain a lower bound involving the quantum metric. For topological flat bands, with an obstruction to localized WFs respecting all symmetries, we again obtain an upper bound for${\stackrel{\u0303}{D}}_{low}$ linear in$\leftU\right$ . We discuss the insights obtained from our bounds by comparing them with meanfield and quantum Monte Carlo results. 
null (Ed.)The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., FOCS 1998 and J. ACM 2001). We find tight or nearly tight bounds on the approximate degree and quantum query complexities of several basic functions. Specifically, we show the following. kDistinctness: For any constant k, the approximate degree and quantum query complexity of the kdistinctness function is Ω(n3/4−1/(2k)). This is nearly tight for large k, as Belovs (FOCS 2012) has shown that for any constant k, the approximate degree and quantum query complexity of kdistinctness is O(n3/4−1/(2k+2−4)). Image size testing: The approximate degree and quantum query complexity of testing the size of the image of a function [n]→[n] is Ω~(n1/2). This proves a conjecture of Ambainis et al. (SODA 2016), and it implies tight lower bounds on the approximate degree and quantum query complexity of the following natural problems. kJunta testing: A tight Ω~(k1/2) lower bound for kjunta testing, answering the main open question of Ambainis et al. (SODA 2016). Statistical distance from uniform: A tight Ω~(n1/2) lower bound for approximating the statistical distance of a distribution from uniform, answering the main question left open by Bravyi et al. (STACS 2010 and IEEE Trans. Inf. Theory 2011). Shannon entropy: A tight Ω~(n1/2) lower bound for approximating Shannon entropy up to a certain additive constant, answering a question of Li and Wu (2017). Surjectivity: The approximate degree of the surjectivity function is Ω~(n3/4). The best prior lower bound was Ω(n2/3). Our result matches an upper bound of O~(n3/4) due to Sherstov (STOC 2018), which we reprove using different techniques. The quantum query complexity of this function is known to be Θ(n) (Beame and Machmouchi, Quantum Inf. Comput. 2012 and Sherstov, FOCS 2015). Our upper bound for surjectivity introduces new techniques for approximating Boolean functions by lowdegree polynomials. Our lower bounds are proved by significantly refining techniques recently introduced by Bun and Thaler (FOCS 2017).more » « less

Abstract Kernelized Gram matrix $W$ constructed from data points $\{x_i\}_{i=1}^N$ as $W_{ij}= k_0( \frac{ \ x_i  x_j \^2} {\sigma ^2} ) $ is widely used in graphbased geometric data analysis and unsupervised learning. An important question is how to choose the kernel bandwidth $\sigma $, and a common practice called selftuned kernel adaptively sets a $\sigma _i$ at each point $x_i$ by the $k$nearest neighbor (kNN) distance. When $x_i$s are sampled from a $d$dimensional manifold embedded in a possibly highdimensional space, unlike with fixedbandwidth kernels, theoretical results of graph Laplacian convergence with selftuned kernels have been incomplete. This paper proves the convergence of graph Laplacian operator $L_N$ to manifold (weighted)Laplacian for a new family of kNN selftuned kernels $W^{(\alpha )}_{ij} = k_0( \frac{ \ x_i  x_j \^2}{ \epsilon \hat{\rho }(x_i) \hat{\rho }(x_j)})/\hat{\rho }(x_i)^\alpha \hat{\rho }(x_j)^\alpha $, where $\hat{\rho }$ is the estimated bandwidth function by kNN and the limiting operator is also parametrized by $\alpha $. When $\alpha = 1$, the limiting operator is the weighted manifold Laplacian $\varDelta _p$. Specifically, we prove the pointwise convergence of $L_N f $ and convergence of the graph Dirichlet form with rates. Our analysis is based on first establishing a $C^0$ consistency for $\hat{\rho }$ which bounds the relative estimation error $\hat{\rho }  \bar{\rho }/\bar{\rho }$ uniformly with high probability, where $\bar{\rho } = p^{1/d}$ and $p$ is the data density function. Our theoretical results reveal the advantage of the selftuned kernel over the fixedbandwidth kernel via smaller variance error in lowdensity regions. In the algorithm, no prior knowledge of $d$ or data density is needed. The theoretical results are supported by numerical experiments on simulated data and handwritten digit image data.more » « less