Finite-rate sparse quantum codes aplenty
- URL: http://arxiv.org/abs/2207.03562v3
- Date: Fri, 14 Apr 2023 00:39:17 GMT
- Title: Finite-rate sparse quantum codes aplenty
- Authors: Maxime Tremblay, Guillaume Duclos-Cianci, Stefanos Kourtis
- Abstract summary: We introduce a methodology for generating random multi-qubit stabilizer codes based on solving a constraint satisfaction problem (CSP) on random bipartite graphs.
Using a state-of-the-art CSP solver, we obtain convincing evidence for the existence of a satisfiability threshold.
We observe that the sparse codes found in the satisfiable phase practically achieve the channel capacity for erasure noise.
- Score: 1.1279808969568252
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a methodology for generating random multi-qubit stabilizer codes
based on solving a constraint satisfaction problem (CSP) on random bipartite
graphs. This framework allows us to enforce stabilizer commutation, $X/Z$
balancing, finite rate, sparsity, and maximum-degree constraints simultaneously
in a CSP that we can then solve numerically. Using a state-of-the-art CSP
solver, we obtain convincing evidence for the existence of a satisfiability
threshold. Furthermore, the extent of the satisfiable phase increases with the
number of qubits. In that phase, finding sparse codes becomes an easy problem.
Moreover, we observe that the sparse codes found in the satisfiable phase
practically achieve the channel capacity for erasure noise. Our results show
that intermediate-size finite-rate sparse quantum codes are easy to find, while
also demonstrating a flexible methodology for generating good codes with custom
properties. We therefore establish a complete and customizable pipeline for
random quantum code discovery.
Related papers
- Non-local resources for error correction in quantum LDPC codes [0.0]
Surface code suffers from a low encoding rate, requiring a vast number of physical qubits for large-scale quantum computation.
hypergraph product codes present a promising alternative, as both their encoding rate and distance scale with block size.
Recent advancements have shown how to deterministically perform high-fidelity cavity enabled non-local many-body gates.
arXiv Detail & Related papers (2024-09-09T17:28:41Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
We consider clipped optimization problems with heavy-tailed noise with structured density.
We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order.
We prove that the resulting estimates have negligible bias and controllable variance.
arXiv Detail & Related papers (2023-11-07T17:39:17Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
We present quantum algorithms for sampling from nonlogconcave probability distributions.
$f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
arXiv Detail & Related papers (2023-10-17T17:55:32Z) - Robust sparse IQP sampling in constant depth [3.670008893193884]
NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation.
We propose a scheme to achieve a provable superpolynomial quantum advantage that is robust to noise with minimal error correction requirements.
arXiv Detail & Related papers (2023-07-20T09:41:08Z) - Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks [0.0]
We show that a simple telescoping sum trick, together with the triangle inequality and a tensorisation property of expected-contractive coefficients of random channels, allow us to achieve general simultaneous decoupling for multiple users via local actions.
We obtain bounds on the expected deviation from ideal decoupling either in the one-shot setting in terms of smooth min-entropies, or the finite block length setting in terms of R'enyi entropies.
This leads to one-shot, finite block length, and simultaneous achievability results for several tasks in quantum Shannon theory.
arXiv Detail & Related papers (2023-04-24T14:17:32Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients.
We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage.
Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
arXiv Detail & Related papers (2022-12-12T15:06:32Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete.
We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes.
Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
arXiv Detail & Related papers (2021-08-10T15:00:20Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP)
This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm.
Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
arXiv Detail & Related papers (2021-05-06T17:59:38Z)
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.