Quantum LDPC Codes with Almost Linear Minimum Distance

• URL: http://arxiv.org/abs/2012.04068v2
• Date: Sun, 3 Oct 2021 18:58:06 GMT
• Title: Quantum LDPC Codes with Almost Linear Minimum Distance
• Authors: Pavel Panteleev and Gleb Kalachev
• Abstract summary: 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$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a construction of quantum LDPC codes of dimension $\Theta(\log N)$ and distance $\Theta(N/\log N)$ as the code length $N\to\infty$. Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance $\Omega(N^{1-\alpha/2}/\log N)$ and dimension $\Omega(N^\alpha \log N)$, where $0 \le \alpha < 1$. We also introduce and study a new operation called lifted product, which naturally generalizes the product operations for quantum codes and chain complexes. Moreover, as a simple byproduct of our results on quantum codes, we obtain a new result on classical codes. We show that for any fixed $R < 1$ there exists an asymptotically good family of classical quasi-cyclic LDPC codes of rate at least $R$ with, in some sense, optimal circulant size $\Omega(N/\log N)$ as the code length $N\to\infty$.

Related papers

• Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes [0.9208007322096533]
  We construct an explicit infinite family of quantum LDPC codes supporting a $Cr-1Z$ gate with length $N$, dimension $Kgeq N1-epsilon$, distance $Dgeq N1/r/namepoly(log N)$, and stabilizer weight $wleqoperatorname(log N)$.
  arXiv  Detail & Related papers  (2024-10-18T17:52:59Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• 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)
• 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)
• 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)
• Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically [36.685393265844986]
  We construct new families of quantum error correction codes achieving the quantum-Omega-Varshamov boundally. $mathscrQ$ can be encoded very efficiently by circuits of size $O(N)$ and depth $O(sqrtN)$. $mathscrQ$ can also be decoded in parallel in $O(sqrtN)$ time by using $O(sqrtN)$ classical processors.
  arXiv  Detail & Related papers  (2021-07-12T03:27:30Z)
• Balanced Product Quantum Codes [5.33024001730262]
  This work provides the first explicit and non-random family of $[[N,K,D]]$ LDPC quantum codes. The family is constructed by amalgamating classical codes and Ramanujan graphs via an operation called balanced product.
  arXiv  Detail & Related papers  (2020-12-16T21:19:38Z)
• Fiber Bundle Codes: Breaking the $N^{1/2} \operatorname{polylog}(N)$ Barrier for Quantum LDPC Codes [1.2246649738388389]
  We present a quantum LDPC code family that has distance greater than $Omega(N3/5/operatornamepolylog(N))$. This is the first quantum LDPC code construction which achieves distance greater than $N1/2 operatornamepolylog(N)$.
  arXiv  Detail & Related papers  (2020-09-08T18:00:07Z)
• 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 Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

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.