ﻻ يوجد ملخص باللغة العربية
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 queries. In the quantum setting, Approximate Counting can be done with $Oleft(minleft(sqrt{N/epsilon}, sqrt{N/K}/epsilonright)right)$ queries. It has recently been shown that this can be achieved by a simple algorithm that only uses Grover iterations; however the algorithm performs these iterations adaptively. Motivated by concerns of computational simplicity, we consider algorithms that use Grover iterations with limited adaptivity. We show that algorithms using only nonadaptive Grover iterations can achieve $Oleft(sqrt{N/epsilon}right)$ query complexity, which is tight.
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}{vare
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 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
We consider the Grover search algorithm implementation for a quantum register of size $N = 2^k$ using k (or k +1) microwave- and laser-driven Rydberg-blockaded atoms, following the proposal by M{o}lmer, Isenhower, and Saffman [J. Phys. B 44, 184016 (
The final goal of quantum hypothesis testing is to achieve quantum advantage over all possible classical strategies. In the protocol of quantum reading this advantage is achieved for information retrieval from an optical memory, whose generic cell st