



@article {2174,
	title = {Faster quantum simulation by randomization},
	journal = {Quantum },
	volume = {3},
	year = {2019},
	month = {08/28/2019},
	abstract = {<p><span style="font-family: \&quot;Lucida Grande\&quot;, helvetica, arial, verdana, sans-serif; font-size: 14.4px;">Product formulas can be used to simulate Hamiltonian dynamics on a quantum computer by approximating the exponential of a sum of operators by a product of exponentials of the individual summands. This approach is both straightforward and surprisingly efficient. We show that by simply randomizing how the summands are ordered, one can prove stronger bounds on the quality of approximation and thereby give more efficient simulations. Indeed, we show that these bounds can be asymptotically better than previous bounds that exploit commutation between the summands, despite using much less information about the structure of the Hamiltonian. Numerical evidence suggests that our randomized algorithm may be advantageous even for near-term quantum simulation.</span></p>},
	doi = {https://doi.org/10.22331/q-2019-09-02-182},
	url = {https://arxiv.org/abs/1805.08385},
	author = {Andrew M. Childs and Aaron Ostrander and Yuan Su}
}
@article {1244,
	title = {A framework for bounding nonlocality of state discrimination},
	journal = {Communications in Mathematical Physics},
	volume = {323},
	year = {2013},
	month = {2013/9/4},
	pages = {1121 - 1153},
	abstract = {  We consider the class of protocols that can be implemented by local quantum
operations and classical communication (LOCC) between two parties. In
particular, we focus on the task of discriminating a known set of quantum
states by LOCC. Building on the work in the paper "Quantum nonlocality without
entanglement" [BDF+99], we provide a framework for bounding the amount of
nonlocality in a given set of bipartite quantum states in terms of a lower
bound on the probability of error in any LOCC discrimination protocol. We apply
our framework to an orthonormal product basis known as the domino states and
obtain an alternative and simplified proof that quantifies its nonlocality. We
generalize this result for similar bases in larger dimensions, as well as the
"rotated" domino states, resolving a long-standing open question [BDF+99].
},
	doi = {10.1007/s00220-013-1784-0},
	url = {http://arxiv.org/abs/1206.5822v1},
	author = {Andrew M. Childs and Debbie Leung and Laura Mancinska and Maris Ozols}
}
@article {1240,
	title = {From optimal measurement to efficient quantum algorithms for the hidden  subgroup problem over semidirect product groups
},
	year = {2005},
	month = {2005/04/11},
	abstract = {  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.
},
	doi = {10.1109/SFCS.2005.38},
	url = {http://arxiv.org/abs/quant-ph/0504083v2},
	author = {Dave Bacon and Andrew M. Childs and Wim van Dam}
}
@article {1237,
	title = {Finding cliques by quantum adiabatic evolution},
	year = {2000},
	month = {2000/12/19},
	abstract = {  Quantum adiabatic evolution provides a general technique for the solution of
combinatorial search problems on quantum computers. We present the results of a
numerical study of a particular application of quantum adiabatic evolution, the
problem of finding the largest clique in a random graph. An n-vertex random
graph has each edge included with probability 1/2, and a clique is a completely
connected subgraph. There is no known classical algorithm that finds the
largest clique in a random graph with high probability and runs in a time
polynomial in n. For the small graphs we are able to investigate (n <= 18), the
quantum algorithm appears to require only a quadratic run time.
},
	url = {http://arxiv.org/abs/quant-ph/0012104v1},
	author = {Andrew M. Childs and Edward Farhi and Jeffrey Goldstone and Sam Gutmann}
}
