Efficient Quantum State Preparation with Walsh Series

• URL: http://arxiv.org/abs/2307.08384v3
• Date: Thu, 9 Nov 2023 20:31:47 GMT
• Title: Efficient Quantum State Preparation with Walsh Series
• Abstract summary: A new approximate Quantum State Preparation (QSP) method is introduced, called the Walsh Series Loader (WSL) WSL approximates quantum states defined by real-valued functions of single real variables with a depth independent of the number $n$ of qubits.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: A new approximate Quantum State Preparation (QSP) method is introduced, called the Walsh Series Loader (WSL). The WSL approximates quantum states defined by real-valued functions of single real variables with a depth independent of the number $n$ of qubits. Two approaches are presented: the first one approximates the target quantum state by a Walsh Series truncated at order $O(1/\sqrt{\epsilon})$, where $\epsilon$ is the precision of the approximation in terms of infidelity. The circuit depth is also $O(1/\sqrt{\epsilon})$, the size is $O(n+1/\sqrt{\epsilon})$ and only one ancilla qubit is needed. The second method represents accurately quantum states with sparse Walsh series. The WSL loads $s$-sparse Walsh Series into $n$-qubits with a depth doubly-sparse in $s$ and $k$, the maximum number of bits with value $1$ in the binary decomposition of the Walsh function indices. The associated quantum circuit approximates the sparse Walsh Series up to an error $\epsilon$ with a depth $O(sk)$, a size $O(n+sk)$ and one ancilla qubit. In both cases, the protocol is a Repeat-Until-Success (RUS) procedure with a probability of success $P=\Theta(\epsilon)$, giving an averaged total time of $O(1/\epsilon^{3/2})$ for the WSL (resp. $O(sk/\epsilon)$ for the sparse WSL). Amplitude amplification can be used to reduce by a factor $O(1/\sqrt{\epsilon})$ the total time dependency with $\epsilon$ but increases the size and depth of the associated quantum circuits, making them linearly dependent on $n$. These protocols give overall efficient algorithms with no exponential scaling in any parameter. They can be generalized to any complex-valued, multi-variate, almost-everywhere-differentiable function. The Repeat-Until-Success Walsh Series Loader is so far the only method which prepares a quantum state with a circuit depth and an averaged total time independent of the number of qubits.

Related papers

• Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
  We propose a quantum multi-level estimation framework for a functional $sum_i=1n f(p_i)$ of a discrete distribution.<n>We present efficient quantum estimators for the $q$-Tsallis entropy of discrete distributions.
  arXiv  Detail & Related papers  (2026-05-05T12:25:17Z)
• Quantum Sketches, Hashing, and Approximate Nearest Neighbors [0.0]
  In a broad quantum sketch model, the dataset $P$ is encoded as an $m$-qubit state $_P$, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of $_P$.<n>For every approximation factor $cge 1$ and constant success probability $p>1/2$, we exhibit $n$-point instances in Hamming space $0,1d$ with $d=(log n)$ for which any such sketch requires $m=(n)$ qubits.
  arXiv  Detail & Related papers  (2026-02-22T16:18:36Z)
• Tight Success Probabilities for Quantum Period Finding and Phase Estimation [2.2329417756084093]
  We consider a general post-processing algorithm which succeeds whenever the measured $hatell$ is within some tolerance $M$ of a positive integer multiple of $2n / r$.<n>We give new (tight) lower and upper bounds on the success probability that converge to 1.<n>Our analysis allows for the careful exploitation of the tradeoffs between the complexity of the quantum circuit and the effort spent in classical processing when optimizing the probability of success.
  arXiv  Detail & Related papers  (2025-06-25T15:14:59Z)
• Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation [5.755460769073285]
  Dicke states represent an important class of entangled quantum states with broad applications in quantum computing.<n>We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints.
  arXiv  Detail & Related papers  (2025-05-21T11:55:17Z)
• Circuit Complexity of Sparse Quantum State Preparation [0.0]
  We show that any $n$-qubit $d$-sparse quantum state can be prepared by a quantum circuit of size $O(fracdnlog d)$ and depth $Theta(log dn)$ using at most $O(fracndlog d )$ ancillary qubits. We also establish the lower bound $Omega(fracdnlog(n + m) + log d + n)$ on the circuit size with $m$ ancillary qubits available.
  arXiv  Detail & Related papers  (2024-06-23T15:28:20Z)
• 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)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model. Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$. Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
  arXiv  Detail & Related papers  (2023-08-16T06:46:37Z)
• 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)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• 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)
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
  The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $psi_vrangle$ in depth. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime.
  arXiv  Detail & Related papers  (2021-08-13T09:47:11Z)
• Low-depth Quantum State Preparation [3.540171881768714]
  A crucial subroutine in quantum computing is to load the classical data of $N$ complex numbers into the amplitude of a superposed $n=lceil logNrceil$-qubit state. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with $mathcal O(n2)$ circuit depth to encode any $N$ complex numbers.
  arXiv  Detail & Related papers  (2021-02-15T13:11:43Z)
• Quantum coding with low-depth random circuits [2.4201087215689947]
  We use ensembles of low-depth random circuits with local connectivity to generate quantum error-correcting codes. For random stabilizer codes and the erasure channel, we find strong evidence that a depth $O(log N)$ random circuit is necessary. These results indicate that finite-rate quantum codes are practically relevant for near-term devices.
  arXiv  Detail & Related papers  (2020-10-19T18:25:30Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  We first prove a simple variant of the vanilla coordinate ascent, called Coordinate-Ascent+. We then propose Coordinate-Ascent++, that achieves tight $(1-1/e-varepsilon)$-approximation guarantee while performing the same number of iterations. The computation of each round of Coordinate-Ascent++ can be easily parallelized so that the computational cost per machine scales as $O(n/sqrtvarepsilon+nlog n)$.
  arXiv  Detail & Related papers  (2020-06-21T06:57:59Z)
• 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)

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.