@article {2530, title = {Quantum Computer Systems for Scientific Discovery}, year = {2019}, month = {12/16/2019}, abstract = {

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.

}, url = {https://arxiv.org/abs/1912.07577}, author = {Yuri Alexeev and Dave Bacon and Kenneth R. Brown and Robert Calderbank and Lincoln D. Carr and Frederic T. Chong and Brian DeMarco and Dirk Englund and Edward Farhi and Bill Fefferman and Alexey V. Gorshkov and Andrew Houck and Jungsang Kim and Shelby Kimmel and Michael Lange and Seth Lloyd and Mikhail D. Lukin and Dmitri Maslov and Peter Maunz and Christopher Monroe and John Preskill and Martin Roetteler and Martin Savage and Jeff Thompson and Umesh Vazirani} } @article {1989, title = {Quantum Algorithms for Graph Connectivity and Formula Evaluation}, year = {2017}, month = {2017/04/03}, abstract = {

We give a new upper bound on the quantum query complexity of deciding st-connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm for st-connectivity to Boolean formula evaluation problems, we match the O( \√ N) bound on the quantum query complexity of evaluating formulas on N variables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that this st-connectivity-based approach may be the \“right\” way of looking at quantum algorithms for formula evaluation.

}, url = {https://arxiv.org/abs/1704.00765}, author = {Stacey Jeffery and Shelby Kimmel} } @article {1733, title = {A Quantum Version of Sch{\"o}ning{\textquoteright}s Algorithm Applied to Quantum 2-SAT}, journal = {Quantum Information and Computation}, volume = {16}, year = {2016}, month = {2016/03/22}, abstract = {

We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves this decision problem with high probability for n qubits, L clauses, and promise gap c in time O(n^2 L^2 c^{-2}). If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Sch\"oning\&$\#$39;s probabilistic algorithm for k-SAT.

}, url = {http://arxiv.org/abs/1603.06985}, author = {Edward Farhi and Shelby Kimmel and Kristan Temme} } @article {1596, title = {Quantum Compressed Sensing Using 2-Designs}, year = {2015}, month = {2015/10/29}, abstract = {We develop a method for quantum process tomography that combines the efficiency of compressed sensing with the robustness of randomized benchmarking. Our method is robust to state preparation and measurement errors, and it achieves a quadratic speedup over conventional tomography when the unknown process is a generic unitary evolution. Our method is based on PhaseLift, a convex programming technique for phase retrieval. We show that this method achieves approximate recovery of almost all signals, using measurements sampled from spherical or unitary 2-designs. This is the first positive result on PhaseLift using 2-designs. We also show that exact recovery of all signals is possible using unitary 4-designs. Previous positive results for PhaseLift required spherical 4-designs, while PhaseLift was known to fail in certain cases when using spherical 2-designs.}, url = {http://arxiv.org/abs/1510.08887}, author = {Shelby Kimmel and Yi-Kai Liu} } @article {1592, title = {Quantum vs Classical Proofs and Subset Verification}, year = {2015}, month = {2015/10/22}, abstract = {We study the ability of efficient quantum verifiers to decide properties of exponentially large subsets given either a classical or quantum witness. We develop a general framework that can be used to prove that QCMA machines, with only classical witnesses, cannot verify certain properties of subsets given implicitly via an oracle. We use this framework to prove an oracle separation between QCMA and QMA using an {\textquoteleft}{\textquoteleft}in-place{\textquoteright}{\textquoteright} permutation oracle, making the first progress on this question since Aaronson and Kuperberg in 2007. We also use the framework to prove a particularly simple standard oracle separation between QCMA and AM.}, url = {http://arxiv.org/abs/1510.06750}, author = {Bill Fefferman and Shelby Kimmel} } @article {1508, title = {Quantum Adversary (Upper) Bound}, journal = {Chicago Journal of Theoretical Computer Science}, volume = {19}, year = {2013}, month = {2013/04/05}, pages = {1 - 14}, abstract = { We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound. This nonconstructive method can give an upper bound on query complexity without producing an algorithm. For example, we describe an oracle problem which we prove (non-constructively) can be solved in $O(1)$ queries, where the previous best quantum algorithm uses a polylogarithmic number of queries. We then give an explicit $O(1)$-query algorithm for this problem based on span programs. }, doi = {10.4086/cjtcs.2013.004}, url = {http://arxiv.org/abs/1101.0797v5}, author = {Shelby Kimmel} } @article {1222, title = {The quantum query complexity of read-many formulas}, journal = {Lecture Notes in Computer Science}, volume = {7501}, year = {2012}, month = {2012/09/10}, pages = {337-348}, abstract = { The quantum query complexity of evaluating any read-once formula with n black-box input bits is Theta(sqrt(n)). However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with n inputs, size S, and G gates using O(min{n, sqrt{S}, n^{1/2} G^{1/4}}) quantum queries. Furthermore, we show that this algorithm is optimal, since for any n,S,G there exists a formula with n inputs, size at most S, and at most G gates that requires Omega(min{n, sqrt{S}, n^{1/2} G^{1/4}}) queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth k >= 3, and we give a linear-size circuit of depth 2 that requires Omega (n^{5/9}) queries. Applications of these results include a Omega (n^{19/18}) lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including PARITY, and a construction of an AC^0 circuit of linear size that can only be evaluated by a formula with Omega(n^{2-epsilon}) gates. }, doi = {10.1007/978-3-642-33090-2_30}, url = {http://arxiv.org/abs/1112.0548v1}, author = {Andrew M. Childs and Shelby Kimmel and Robin Kothari} }