



01947nas a2200397   4500008004100000245005400041210005400095260001500149520085000164100001801014700001601032700002301048700002301071700002201094700002401116700001901140700001801159700001801177700002001195700002501215700001801240700001801258700001901276700001901295700001601314700002301330700001901353700001701372700002401389700001901413700002201432700001901454700001901473700002001492856003701512       2019                        eng d00aQuantum Computer Systems for Scientific Discovery0 aQuantum Computer Systems for Scientific Discovery  c12/16/20193 a<p>The great promise of quantum computers comes with the dual challenges of building them and finding their useful applications. We argue that these two challenges should be considered together, by co-designing full stack quantum computer systems along with their applications in order to hasten their development and potential for scientific discovery. In this context, we identify scientific and community needs, opportunities, and significant challenges for the development of quantum computers for science over the next 2-10 years. This document is written by a community of university, national laboratory, and industrial researchers in the field of Quantum Information Science and Technology, and is based on a summary from a U.S. National Science Foundation workshop on Quantum Computing held on October 21-22, 2019 in Alexandria, VA.</p>1 aAlexeev, Yuri1 aBacon, Dave1 aBrown, Kenneth, R.1 aCalderbank, Robert1 aCarr, Lincoln, D.1 aChong, Frederic, T.1 aDeMarco, Brian1 aEnglund, Dirk1 aFarhi, Edward1 aFefferman, Bill1 aGorshkov, Alexey, V.1 aHouck, Andrew1 aKim, Jungsang1 aKimmel, Shelby1 aLange, Michael1 aLloyd, Seth1 aLukin, Mikhail, D.1 aMaslov, Dmitri1 aMaunz, Peter1 aMonroe, Christopher1 aPreskill, John1 aRoetteler, Martin1 aSavage, Martin1 aThompson, Jeff1 aVazirani, Umesh  uhttps://arxiv.org/abs/1912.0757701370nas 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/0501044v201258nas a2200181   4500008004100000245005500041210005500096260001400151490000700165520074300172100001600915700002300931700002200954700001700976700002200993700001701015856004401032       2001                        eng d00aUniversal simulation of Markovian quantum dynamics0 aUniversal simulation of Markovian quantum dynamics  c2001/11/90 v643 a  Although the conditions for performing arbitrary unitary operations to
simulate the dynamics of a closed quantum system are well understood, the same
is not true of the more general class of quantum operations (also known as
superoperators) corresponding to the dynamics of open quantum systems. We
propose a framework for the generation of Markovian quantum dynamics and study
the resources needed for universality. For the case of a single qubit, we show
that a single nonunitary process is necessary and sufficient to generate all
unital Markovian quantum dynamics, whereas a set of processes parametrized by
one continuous parameter is needed in general. We also obtain preliminary
results for the unital case in higher dimensions.
1 aBacon, Dave1 aChilds, Andrew, M.1 aChuang, Isaac, L.1 aKempe, Julia1 aLeung, Debbie, W.1 aZhou, Xinlan  uhttp://arxiv.org/abs/quant-ph/0008070v2