Locality vs Quantum Codes

• URL: http://arxiv.org/abs/2409.15203v1
• Date: Mon, 23 Sep 2024 16:50:21 GMT
• Title: Locality vs Quantum Codes
• Authors: Samuel Dai, Ray Li,
• Abstract summary: Quantum codes give a promising avenue towards quantum fault tolerance, but the practical constraint of locality limits their quality. This paper proves optimal tradeoffs between the locality and parameters of quantum error-correcting codes.
• Score: 8.747606955991708
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper proves optimal tradeoffs between the locality and parameters of quantum error-correcting codes. Quantum codes give a promising avenue towards quantum fault tolerance, but the practical constraint of locality limits their quality. The seminal Bravyi-Poulin-Terhal (BPT) bound says that a $[[n,k,d]]$ quantum stabilizer code with 2D-locality must satisfy $kd^2\le O(n)$. We answer the natural question: for better code parameters, how much "non-locality" is needed? In particular, (i) how long must the long-range interactions be, and (ii) how many long-range interactions must there be? We give a complete answer to both questions for all $n,k,d$: above the BPT bound, any 2D-embedding must have at least $\Omega(\#^*)$ interactions of length $\Omega(\ell^*)$, where $\#^*= \max(k,d)$ and $\ell^*=\max\big(\frac{d}{\sqrt{n}}, \big( \frac{kd^2}{n} \big)^{1/4} \big)$. Conversely, we exhibit quantum codes that show, in strong ways, that our interaction length $\ell^*$ and interaction count $\#^*$ are asymptotically optimal for all $n,k,d$. Our results generalize or improve all prior works on this question, including the BPT bound and the results of Baspin and Krishna. One takeaway of our work is that, for any desired distance $d$ and dimension $k$, the number of long-range interactions is asymptotically minimized by a good qLDPC code of length $\Theta(\max(k,d))$. Following Baspin and Krishna, we also apply our results to the codes implemented in the stacked architecture and obtain better bounds. In particular, we rule out any implementation of hypergraph product codes in the stacked architecture.

Related papers

• Stabilizer codes for Heisenberg-limited many-body Hamiltonian estimation [0.0]
  We study the performance of stabilizer quantum error correcting codes in estimating many-body Hamiltonians under noise. We showcase three families of stabilizer codes that achieve the scalings of $(nt)-1$, $(n2t)-1$ and $(n3t)-1$, respectively.
  arXiv  Detail & Related papers  (2024-08-20T18:00:09Z)
• Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
  We revisit certain problems of pose estimation based on 3D--2D correspondences between features which may be points or lines. We show experimentally that the resulting solvers are numerically stable and fast.
  arXiv  Detail & Related papers  (2024-04-25T12:09:16Z)
• Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code [0.0]
  We demonstrate that a high fidelity approximation to $| Psi_b rangle$ can be efficiently constructed by a quantum circuit. The technique used to construct these states is of interest and hopefully will have applications beyond codes.
  arXiv  Detail & Related papers  (2024-04-24T18:37:15Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• 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)
• Quantifying nonlocality: how outperforming local quantum codes is expensive [0.06091702876917279]
  Quantum low-density parity-check (LDPC) codes are a promising avenue to reduce the cost of constructing scalable quantum circuits. We show that quantum LDPC codes implemented through local interactions obey restrictions on their dimension $k$ and distance $d$. In particular, in 2D we show that a quantum LDPC with distance $n1/2 + epsilon$ code requires $Omega(n1/2 + epsilon)$ interactions of length $widetildeOmega(nepsilon)$.
  arXiv  Detail & Related papers  (2021-09-22T18:55:45Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Quantum LDPC Codes with Almost Linear Minimum Distance [0.0]
  We give a construction of quantum LDPC codes of dimension $Theta(log N)$ and distance $Theta(N/log N)$ as the code length $Ntoinfty$. We show that for any fixed $R 1$ there exists an quasi-cyclically good family of classical LDPC codes of rate at least $R$ with, in some sense, optimal circulant size $Omega(N/log N)$ as the code length $Ntoinfty$.
  arXiv  Detail & Related papers  (2020-12-07T21:20:53Z)
• 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)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  We devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tildeO(N-2/3)$ with privacy guarantees.
  arXiv  Detail & Related papers  (2020-07-23T10:50:42Z)

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.