A Faster Quantum Fourier Transform

• URL: http://arxiv.org/abs/2501.12414v2
• Date: Mon, 10 Feb 2025 05:05:17 GMT
• Title: A Faster Quantum Fourier Transform
• Authors: Ronit Shah,
• Abstract summary: We present anally improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings. We show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits.
• Score: 0.0
• License:
• Abstract: We present an asymptotically improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings. Historically, the approximate QFT has been implemented in $\Theta(n \log n)$ gates, and the exact in $\Theta(n^2)$ gates. In this work, we show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits. Specifically, our approach yields an $\Theta(n(\log \log n)^2)$ algorithm for the approximate QFT using $\Theta(\log n)$ ancillas, and an $\Theta(n(\log n)^2)$ algorithm for the exact QFT requiring $\Theta(n)$ ancillas.

Related papers

• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  We give a conceptually simple quantum linear system solvers (QLSS) that does not use complex or difficult-to-analyze techniques. If the solution norm $lVertboldsymbolxrVert$ is known exactly, our QLSS requires only a single application of kernel. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(kappa)$ complexity can be achieved for norm estimation.
  arXiv  Detail & Related papers  (2024-06-17T20:54:11Z)
• Multidimensional Quantum Fourier Transformation [0.0]
  In this work, the known QFT circuit is used to derive an efficient circuit for the multidimensional QFT. An example on current hardware is depicted by a 6 qubit 2D-QFT with an IBM quantum computer.
  arXiv  Detail & Related papers  (2023-01-31T18:25:40Z)
• Efficiently Computing Sparse Fourier Transforms of $q$-ary Functions [12.522202946750157]
  We develop a sparse Fourier transform algorithm specifically for $q$-ary functions of length $n$ sequences. We show that for fixed $q$, a robust version of $q$-SFT has a sample complexity of $O(Sn2)$ and a computational complexity of $O(Sn3)$ with the same guarantees.
  arXiv  Detail & Related papers  (2023-01-15T22:04:53Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• Modified Iterative Quantum Amplitude Estimation is Asymptotically Optimal [0.37798600249187286]
  We provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) QAE algorithms appear as a subroutine in many applications for quantum computers.
  arXiv  Detail & Related papers  (2022-08-31T03:20:10Z)
• 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)
• T-count optimization of approximate quantum Fourier transform [0.0]
  We present a new n-qubit QFT circuit approximated to error O(varepsilon) using Toffoli gates and quantum adders.
  arXiv  Detail & Related papers  (2022-03-15T09:13:51Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso bandit is an algorithm that estimates the vector defining the reward function as well as its sparse support. We establish non-asymptotic regret upper bounds scaling as $mathcalO( log d + sqrtT )$ in general, and as $mathcalO( log d + sqrtT )$ under the so-called margin condition.
  arXiv  Detail & Related papers  (2020-10-22T19:14:37Z)
• Quantum Legendre-Fenchel Transform [6.643082745560234]
  We present a quantum algorithm to compute the discrete Legendre-Fenchel transform. We show that our quantum algorithm is optimal up to polylogarithmic factors.
  arXiv  Detail & Related papers  (2020-06-08T18:00:05Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

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.