Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code

• URL: http://arxiv.org/abs/2404.16129v1
• Date: Wed, 24 Apr 2024 18:37:15 GMT
• Title: Efficiently constructing a quantum uniform superposition over bit strings near a binary linear code
• Authors: Edward Farhi, Stephen P. Jordan,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We demonstrate that a high fidelity approximation to $| \Psi_b \rangle$, the quantum superposition over all bit strings within Hamming distance $b$ of the codewords of a dimension-$k$ linear code over $\mathbb{Z}_2^n$, 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 $\mathbb{R}^n$, $|\Psi_b \rangle$ 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.

Related papers

• Far from Perfect: Quantum Error Correction with (Hyperinvariant) Evenbly Codes [38.729065908701585]
  We introduce a new class of qubit codes that we call Evenbly codes. Our work indicates that Evenbly codes may show promise for practical quantum computing applications.
  arXiv  Detail & Related papers  (2024-07-16T17:18:13Z)
• Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
  We establish connections between state tomography, pseudorandomness, quantum state, circuit lower bounds. We show that even slightly non-trivial quantum state tomography algorithms would lead to new statements about quantum state synthesis.
  arXiv  Detail & Related papers  (2024-05-16T16:46:27Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
  We consider the preparation for $n$-qubit sparse quantum states with $s$ non-zero amplitudes and propose two algorithms. The first algorithm uses $O(ns/log n + n)$ gates, improving upon previous methods by $O(log n)$. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path.
  arXiv  Detail & Related papers  (2024-04-08T02:13:40Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
  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.
  arXiv  Detail & Related papers  (2022-10-20T19:35:50Z)
• 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)
• 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 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)
• Quantum $k$-nearest neighbors algorithm [0.0]
  We present a quantum analog of classical $k$NN $-$ quantum $k$NN (Q$k$NN) $-$ based on fidelity as the similarity measure. Unlike classical $k$NN and existing quantum $k$NN algorithms, the proposed algorithm can be directly used on quantum data.
  arXiv  Detail & Related papers  (2020-03-20T10:48:57Z)

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.