2024/04/24 by Edward Farhi, Stephen P. Jordan, Farhi, Edward +1
Computer Science · #Coding theory and cryptography #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2404.16129
openalex publication_date 2024/04/24 · openalex created_date 2024/04/27 · openalex updated_date 2026/07/28
We demonstrate that a high fidelity approximation to | Ψb ⟩, the quantum superposition over all bit strings within Hamming distance b of the codewords of a dimension-k linear code over ℤ2n, can be efficiently constructed by a quantum circuit for large values of n, b and k which we characterize. We do numerical experiments at n=1000 which back up our claims. The achievable radius b is much larger than the distance out to which known classical algorithms can efficiently find the nearest codeword. Hence, these states cannot be prepared by quantum constuctions that require uncomputing to find the codeword nearest a string. Unlike the analogous states for lattices in ℝn, |Ψb ⟩ is not a useful resource for bounded distance decoding because the relevant overlap falls off too quickly with distance and known classical algorithms do better. Furthermore the overlap calculation can be dequantized. Perhaps these states could be used to solve other code problems. The technique used to construct these states is of interest and hopefully will have applications beyond codes.