Quantifying nonlocality: how outperforming local quantum codes is expensive

• URL: http://arxiv.org/abs/2109.10982v1
• Date: Wed, 22 Sep 2021 18:55:45 GMT
• Title: Quantifying nonlocality: how outperforming local quantum codes is expensive
• Authors: Nou\'edyn Baspin, Anirudh Krishna
• Abstract summary: 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)$.
• Score: 0.06091702876917279
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum low-density parity-check (LDPC) codes are a promising avenue to reduce the cost of constructing scalable quantum circuits. However, it is unclear how to implement these codes in practice. Seminal results of Bravyi & Terhal, and Bravyi, Poulin & Terhal have shown that quantum LDPC codes implemented through local interactions obey restrictions on their dimension $k$ and distance $d$. Here we address the complementary question of how many long-range interactions are required to implement a quantum LDPC code with parameters $k$ and $d$. In particular, in 2D we show that a quantum LDPC with distance $n^{1/2 + \epsilon}$ code requires $\Omega(n^{1/2 + \epsilon})$ interactions of length $\widetilde{\Omega}(n^{\epsilon})$. Further a code satisfying $k \propto n$ with distance $d \propto n^\alpha$ requires $\widetilde{\Omega}(n)$ interactions of length $\widetilde{\Omega}(n^{\alpha/2})$. Our results are derived using bounds on quantum codes from graph metrics. As an application of these results, we consider a model called a stacked architecture, which has previously been considered as a potential way to implement quantum LDPC codes. In this model, although most interactions are local, a few of them are allowed to be very long. We prove that limited long-range connectivity implies quantitative bounds on the distance and code dimension.

Related papers

• Locality vs Quantum Codes [8.747606955991708]
  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.
  arXiv  Detail & Related papers  (2024-09-23T16:50:21Z)
• SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
  We present Safe Surgery by Identifying Pushouts (SSIP), an open-source lightweight Python package for automating surgery between qubit CSS codes. Under the hood, it performs linear algebra over $mathbbF$ governed by universal constructions in the category of chain complexes. We show that various logical measurements can be performed cheaply by surgery without sacrificing the high code distance.
  arXiv  Detail & Related papers  (2024-07-12T16:50:01Z)
• 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)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Improved rate-distance trade-offs for quantum codes with restricted connectivity [34.95121779484252]
  We study how the connectivity graph associated with a quantum code constrains the code parameters. We establish a tighter dimension-distance trade-off as a function of the size of separators in the connectivity graph.
  arXiv  Detail & Related papers  (2023-07-06T20:38:34Z)
• 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)
• Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes [0.0]
  We establish lower bounds on the size of Clifford circuits that measure a family of commuting Pauli operators. For local-expander quantum codes, we prove that any syndrome extraction circuit implemented with local Clifford gates has depth at least $Omega(n/sqrtN)$. This suggests that quantum LDPC codes are impractical with 2D local quantum hardware.
  arXiv  Detail & Related papers  (2021-09-29T17:52:16Z)
• 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)
• 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)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.