An Efficient Quantum Decoder for Prime-Power Fields

• URL: http://arxiv.org/abs/2210.11552v2
• Date: Tue, 12 Sep 2023 15:12:16 GMT
• Title: An Efficient Quantum Decoder for Prime-Power Fields
• Authors: Lior Eldar
• Abstract summary: We show that for $q = pm$ where $p$ is small relative to the code block-size $n$, there is a quantum algorithm that solves the problem in time. On the other hand, classical algorithms can efficiently solve the problem only for much smaller inverse factors.
• Score: 1.0878040851638
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We consider a version of the nearest-codeword problem on finite fields $\mathbb{F}_q$ using the Manhattan distance, an analog of the Hamming metric for non-binary alphabets. Similarly to other lattice related problems, this problem is NP-hard even up to constant factor approximation. We show, however, that for $q = p^m$ where $p$ is small relative to the code block-size $n$, there is a quantum algorithm that solves the problem in time ${\rm poly}(n)$, for approximation factor $1/n^2$, for any $p$. On the other hand, to the best of our knowledge, classical algorithms can efficiently solve the problem only for much smaller inverse polynomial factors. Hence, the decoder provides an exponential improvement over classical algorithms, and places limitations on the cryptographic security of large-alphabet extensions of code-based cryptosystems like Classic McEliece.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• 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)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Efficient quantum linear solver algorithm with detailed running costs [0.0]
  We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing. Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
  arXiv  Detail & Related papers  (2023-05-19T00:07:32Z)
• Noisy decoding by shallow circuits with parities: classical and quantum [0.0]
  We show that any classical circuit can correctly recover only a vanishingly small fraction of messages, if the codewords are sent over a noisy channel with positive error rate. We give a simple quantum circuit that correctly decodes the Hadamard code with probability $Omega(varepsilon2)$ even if a $(1/2 - varepsilon)$-fraction of a codeword is adversarially corrupted.
  arXiv  Detail & Related papers  (2023-02-06T15:37:32Z)
• 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)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity.
  arXiv  Detail & Related papers  (2020-12-03T14:03:20Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  We show that a modified greedy algorithm can achieve an approximation factor of $0.305$. We derive a data-dependent upper bound on the optimum. It can also be used to significantly improve the efficiency of such algorithms as branch and bound.
  arXiv  Detail & Related papers  (2020-08-12T15:40:21Z)

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.