



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.0927101122nas a2200145   4500008004100000245004600041210004600087260001400133300001100147490000700158520073400165100002300899700001700922856003700939       2010                        eng d00aQuantum algorithms for algebraic problems0 aQuantum algorithms for algebraic problems  c2010/1/15  a1 - 520 v823 a  Quantum computers can execute algorithms that dramatically outperform
classical computation. As the best-known example, Shor discovered an efficient
quantum algorithm for factoring integers, whereas factoring appears to be
difficult for classical computers. Understanding what other computational
problems can be solved significantly faster using quantum algorithms is one of
the major challenges in the theory of quantum computation, and such algorithms
motivate the formidable task of building a large-scale quantum computer. This
article reviews the current state of quantum algorithms, focusing on algorithms
with superpolynomial speedup over classical computation, and in particular, on
problems with an algebraic flavor.
1 aChilds, Andrew, M.1 avan Dam, Wim  uhttp://arxiv.org/abs/0812.0380v101370nas a2200133   4500008004100000245012700041210006900168260001500237520088400252100001601136700002301152700001701175856004401192       2005                        eng d00aFrom optimal measurement to efficient quantum algorithms for the hidden  subgroup problem over semidirect product groups
0 aFrom optimal measurement to efficient quantum algorithms for the  c2005/04/113 a  We approach the hidden subgroup problem by performing the so-called pretty
good measurement on hidden subgroup states. For various groups that can be
expressed as the semidirect product of an abelian group and a cyclic group, we
show that the pretty good measurement is optimal and that its probability of
success and unitary implementation are closely related to an average-case
algebraic problem. By solving this problem, we find efficient quantum
algorithms for a number of nonabelian hidden subgroup problems, including some
for which no efficient algorithm was previously known: certain metacyclic
groups as well as all groups of the form (Z_p)^r X| Z_p for fixed r (including
the Heisenberg group, r=2). In particular, our results show that entangled
measurements across multiple copies of hidden subgroup states can be useful for
efficiently solving the nonabelian HSP.
1 aBacon, Dave1 aChilds, Andrew, M.1 avan Dam, Wim  uhttp://arxiv.org/abs/quant-ph/0504083v201943nas 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/0501044v201092nas a2200121   4500008004100000245006100041210006100102260001500163520070800178100002300886700001700909856004400926       2005                        eng d00aQuantum algorithm for a generalized hidden shift problem0 aQuantum algorithm for a generalized hidden shift problem  c2005/07/193 a  Consider the following generalized hidden shift problem: given a function f
on {0,...,M-1} x Z_N satisfying f(b,x)=f(b+1,x+s) for b=0,1,...,M-2, find the
unknown shift s in Z_N. For M=N, this problem is an instance of the abelian
hidden subgroup problem, which can be solved efficiently on a quantum computer,
whereas for M=2, it is equivalent to the dihedral hidden subgroup problem, for
which no efficient algorithm is known. For any fixed positive epsilon, we give
an efficient (i.e., poly(log N)) quantum algorithm for this problem provided M
> N^epsilon. The algorithm is based on the "pretty good measurement" and uses
H. Lenstra's (classical) algorithm for integer programming as a subroutine.
1 aChilds, Andrew, M.1 avan Dam, Wim  uhttp://arxiv.org/abs/quant-ph/0507190v1