ﻻ يوجد ملخص باللغة العربية
In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a quantum algorithm for approximate counting. Given a list of $N$ items, $K$ of them marked, their algorithm estimates $K$ to within relative error $varepsilon$ by making only $Oleft( frac{1}{varepsilon}sqrt{frac{N}{K}}right) $ queries. Although this speedup is of Grover type, the BHMT algorithm has the curious feature of relying on the Quantum Fourier Transform (QFT), more commonly associated with Shors algorithm. Is this necessary? This paper presents a simplified algorithm, which we prove achieves the same query complexity using Grover iterations only. We also generalize this to a QFT-free algorithm for amplitude estimation. Related approaches to approximate counting were sketched previously by Grover, Abrams and Williams, Suzuki et al., and Wie (the latter two as we were writing this paper), but in all cases without rigorous analysis.
Approximate Counting refers to the problem where we are given query access to a function $f : [N] to {0,1}$, and we wish to estimate $K = #{x : f(x) = 1}$ to within a factor of $1+epsilon$ (with high probability), while minimizing the number of queri
We prove tight lower bounds for the following variant of the counting problem considered by Aaronson et al. The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k=(1+epsilon)k$. We assume the algorithm has access to
We study the fundamental design automation problem of equivalence checking in the NISQ (Noisy Intermediate-Scale Quantum) computing realm where quantum noise is present inevitably. The notion of approximate equivalence of (possibly noisy) quantum cir
We study quantum algorithms that are given access to trusted and untrusted quantum witnesses. We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer ex
With the advent of gravitational wave detectors employing squeezed light, quantum waveform estimation---estimating a time-dependent signal by means of a quantum-mechanical probe---is of increasing importance. As is well known, backaction of quantum m