



01532nas a2200193   4500008004100000020002200041022001400063245005900077210005900136260001500195300001600210490000700226520098400233100002301217700001701240700001901257700002601276856003601302       2016                        eng d  a978-3-95977-013-2  a1868-896900aOptimal quantum algorithm for polynomial interpolation0 aOptimal quantum algorithm for polynomial interpolation  c2016/03/01  a16:1--16:130 v553 a<p>We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm&#39;s success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability.</p>1 aChilds, Andrew, M.1 avan Dam, Wim1 aHung, Shih-Han1 aShparlinski, Igor, E.  uhttp://arxiv.org/abs/1509.0927101395nas a2200145   4500008004100000245008900041210006900130260001500199300001100214490000700225520094000232100002301172700001801195856003601213       2016                        eng d00aOptimal state discrimination and unstructured search in nonlinear  quantum mechanics0 aOptimal state discrimination and unstructured search in nonlinea  c2016/02/11  a0223140 v933 a  Nonlinear variants of quantum mechanics can solve tasks that are impossible
in standard quantum theory, such as perfectly distinguishing nonorthogonal
states. Here we derive the optimal protocol for distinguishing two states of a
qubit using the Gross-Pitaevskii equation, a model of nonlinear quantum
mechanics that arises as an effective description of Bose-Einstein condensates.
Using this protocol, we present an algorithm for unstructured search in the
Gross-Pitaevskii model, obtaining an exponential improvement over a previous
algorithm of Meyer and Wong. This result establishes a limitation on the
effectiveness of the Gross-Pitaevskii approximation. More generally, we
demonstrate similar behavior under a family of related nonlinearities, giving
evidence that the ability to quickly discriminate nonorthogonal states and
thereby solve unstructured search is a generic feature of nonlinear quantum
mechanics.
1 aChilds, Andrew, M.1 aYoung, Joshua  uhttp://arxiv.org/abs/1507.0633401045nas a2200121   4500008004100000245006200041210006200103260001500165520066900180100002300849700001400872856003700886       2007                        eng d00aOptimal quantum adversary lower bounds for ordered search0 aOptimal quantum adversary lower bounds for ordered search  c2007/08/243 a  The goal of the ordered search problem is to find a particular item in an
ordered list of n items. Using the adversary method, Hoyer, Neerbek, and Shi
proved a quantum lower bound for this problem of (1/pi) ln n + Theta(1). Here,
we find the exact value of the best possible quantum adversary lower bound for
a symmetrized version of ordered search (whose query complexity differs from
that of the original problem by at most 1). Thus we show that the best lower
bound for ordered search that can be proved by the adversary method is (1/pi)
ln n + O(1). Furthermore, we show that this remains true for the generalized
adversary method allowing negative weights.
1 aChilds, Andrew, M.1 aLee, Troy  uhttp://arxiv.org/abs/0708.3396v101943nas a2200133   4500008004100000245006600041210006600107260001500173520152100188100001601709700002301725700001701748856004401765       2005                        eng d00aOptimal measurements for the dihedral hidden subgroup problem0 aOptimal measurements for the dihedral hidden subgroup problem  c2005/01/103 a  We consider the dihedral hidden subgroup problem as the problem of
distinguishing hidden subgroup states. We show that the optimal measurement for
solving this problem is the so-called pretty good measurement. We then prove
that the success probability of this measurement exhibits a sharp threshold as
a function of the density nu=k/log N, where k is the number of copies of the
hidden subgroup state and 2N is the order of the dihedral group. In particular,
for nu<1 the optimal measurement (and hence any measurement) identifies the
hidden subgroup with a probability that is exponentially small in log N, while
for nu>1 the optimal measurement identifies the hidden subgroup with a
probability of order unity. Thus the dihedral group provides an example of a
group G for which Omega(log|G|) hidden subgroup states are necessary to solve
the hidden subgroup problem. We also consider the optimal measurement for
determining a single bit of the answer, and show that it exhibits the same
threshold. Finally, we consider implementing the optimal measurement by a
quantum circuit, and thereby establish further connections between the dihedral
hidden subgroup problem and average case subset sum problems. In particular, we
show that an efficient quantum algorithm for a restricted version of the
optimal measurement would imply an efficient quantum algorithm for the subset
sum problem, and conversely, that the ability to quantum sample from subset sum
solutions allows one to implement the optimal measurement.
1 aBacon, Dave1 aChilds, Andrew, M.1 avan Dam, Wim  uhttp://arxiv.org/abs/quant-ph/0501044v2