Local Quantum Codes from Subdivided Manifolds
- URL: http://arxiv.org/abs/2303.06755v3
- Date: Tue, 20 Jun 2023 15:31:04 GMT
- Title: Local Quantum Codes from Subdivided Manifolds
- Authors: Elia Portnoy
- Abstract summary: We demonstrate the existence of quantum codes which are local in dimension $n$ with $V$ qubits, distance $Vfracn-1n$, and dimension $Vfracn-2n$, up to a $polylog(V)$ factor.
The proof combines the existence ofally good quantum codes, a procedure to build a manifold from a code by Freedman-Hastings, and a quantitative embedding by Gromov-Guth.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For $n \ge 3$, we demonstrate the existence of quantum codes which are local
in dimension $n$ with $V$ qubits, distance $V^{\frac{n-1}{n}}$, and dimension
$V^{\frac{n-2}{n}}$, up to a $polylog(V)$ factor. The distance is optimal up to
the polylog factor. The dimension is also optimal for this distance up to the
polylog factor. The proof combines the existence of asymptotically good quantum
codes, a procedure to build a manifold from a code by Freedman-Hastings, and a
quantitative embedding theorem by Gromov-Guth.
Related papers
- 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) - Geometrically Local Quantum and Classical Codes from Subdivision [10.357542321841887]
A geometrically local quantum code is an error correcting code situated within $mathbbRD$, where the checks only act on qubits within a fixed spatial distance.
Recently, Portnoy made a significant breakthrough with codes achieving optimal dimension and distance up to polylogs.
This paper bypasses this step and streamlines the construction by noticing that a family of good quantum low-density parity-check codes, balanced product codes, naturally carries a two-dimensional structure.
arXiv Detail & Related papers (2023-09-28T02:12:38Z) - 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) - Divide-and-conquer verification method for noisy intermediate-scale
quantum computation [0.0]
noisy intermediate-scale quantum computations can be regarded as logarithmic-depth quantum circuits on a sparse quantum computing chip.
We propose a method to efficiently verify such noisy intermediate-scale quantum computation.
arXiv Detail & Related papers (2021-09-30T08:56:30Z) - 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) - Quantum double aspects of surface code models [77.34726150561087]
We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry.
We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
arXiv Detail & Related papers (2021-06-25T17:03:38Z) - 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) - Quasi-polynomial time algorithms for free quantum games in bounded
dimension [11.56707165033]
We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games.
We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
arXiv Detail & Related papers (2020-05-18T16:55:08Z)
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.