@article {3307, title = {Effect of non-unital noise on random circuit sampling}, year = {2023}, month = {6/28/2023}, abstract = {

In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sources with constant noise rates. We show that even in the presence of unital sources like the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates \— meaning it is never too \"flat\" \— regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As consequences, our results have interesting algorithmic implications on both the hardness and easiness of noisy random circuit sampling, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results.

}, url = {https://arxiv.org/abs/2306.16659}, author = {Bill Fefferman and Soumik Ghosh and Michael Gullans and Kohdai Kuroiwa and Kunal Sharma} } @article {3312, title = {A sharp phase transition in linear cross-entropy benchmarking}, year = {2023}, month = {5/8/2023}, abstract = {

Demonstrations of quantum computational advantage and benchmarks of quantum processors via quantum random circuit sampling are based on evaluating the linear cross-entropy benchmark (XEB). A key question in the theory of XEB is whether it approximates the fidelity of the quantum state preparation. Previous works have shown that the XEB generically approximates the fidelity in a regime where the noise rate per qudit ε satisfies εN<<1 for a system of N qudits and that this approximation breaks down at large noise rates. Here, we show that the breakdown of XEB as a fidelity proxy occurs as a sharp phase transition at a critical value of εN that depends on the circuit architecture and properties of the two-qubit gates, including in particular their entangling power. We study the phase transition using a mapping of average two-copy quantities to statistical mechanics models in random quantum circuit architectures with full or one-dimensional connectivity. We explain the phase transition behavior in terms of spectral properties of the transfer matrix of the statistical mechanics model and identify two-qubit gate sets that exhibit the largest noise robustness.

}, url = {https://arxiv.org/abs/2305.04954}, author = {Brayden Ware and Abhinav Deshpande and Dominik Hangleiter and Pradeep Niroula and Bill Fefferman and Alexey V. Gorshkov and Michael Gullans} } @article {3188, title = {Importance of the Spectral gap in Estimating Ground-State Energies}, journal = {PRX Quantum}, volume = {3}, year = {2022}, month = {12/9/2022}, abstract = {

The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory, with deep implications to both fields. The main object of study is the LocalHamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian and is complete for the class QMA, a quantum generalization of the class NP. A major challenge in the field is to understand the complexity of the LocalHamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in many-body physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum many-body physics, the role played by the spectral gap in the complexity of the LocalHamiltonian is less well-understood. In this work, we make progress on this question by considering the precise regime, in which one estimates the ground-state energy to within inverse exponential precision. Computing ground-state energies precisely is a task that is important for quantum chemistry and quantum many-body physics.
In the setting of inverse-exponential precision, there is a surprising result that the complexity of LocalHamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space. We clarify the reason behind this boost in complexity. Specifically, we show that the full complexity of the high precision case only comes about when the spectral gap is exponentially small. As a consequence of the proof techniques developed to show our results, we uncover important implications for the representability and circuit complexity of ground states of local Hamiltonians, the theory of uniqueness of quantum witnesses, and techniques for the amplification of quantum witnesses in the presence of postselection.

}, doi = {10.1103/prxquantum.3.040327}, url = {https://arxiv.org/abs/2007.11582}, author = {Abhinav Deshpande and Alexey V. Gorshkov and Bill Fefferman} } @article {2983, title = {Quantum computational advantage via high-dimensional Gaussian boson sampling}, journal = {Science Advances}, volume = {8}, year = {2022}, month = {1/5/2022}, pages = {eabi7894}, abstract = {

A programmable quantum computer based on fiber optics outperforms classical computers with a high level of confidence. Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make progress in improving both the theoretical evidence and experimental prospects. We provide evidence for the hardness of GBS, comparable to the strongest theoretical proposals for QCA. We also propose a QCA architecture we call high-dimensional GBS, which is programmable and can be implemented with low loss using few optical components. We show that particular algorithms for simulating GBS are outperformed by high-dimensional GBS experiments at modest system sizes. This work thus opens the path to demonstrating QCA with programmable photonic processors.

}, doi = {10.1126/sciadv.abi7894}, url = {https://www.science.org/doi/abs/10.1126/sciadv.abi7894}, author = {Abhinav Deshpande and Arthur Mehta and Trevor Vincent and Nicolas Quesada and Marcel Hinsche and Marios Ioannou and Lars Madsen and Jonathan Lavoie and Haoyu Qi and Jens Eisert and Dominik Hangleiter and Bill Fefferman and Ish Dhand} } @article {2773, title = {Quantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling}, year = {2021}, month = {2/24/2021}, abstract = {

Photonics is a promising platform for demonstrating quantum computational supremacy (QCS) by convincingly outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing photonics proposals and demonstrations face significant hurdles. Experimentally, current implementations of Gaussian boson sampling lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make significant progress in improving both the theoretical evidence and experimental prospects. On the theory side, we provide strong evidence for the hardness of Gaussian boson sampling, placing it on par with the strongest theoretical proposals for QCS. On the experimental side, we propose a new QCS architecture, high-dimensional Gaussian boson sampling, which is programmable and can be implemented with low loss rates using few optical components. We show that particular classical algorithms for simulating GBS are vastly outperformed by high-dimensional Gaussian boson sampling experiments at modest system sizes. This work thus opens the path to demonstrating QCS with programmable photonic processors.

}, url = {https://arxiv.org/abs/2102.12474}, author = {Abhinav Deshpande and Arthur Mehta and Trevor Vincent and Nicolas Quesada and Marcel Hinsche and Marios Ioannou and Lars Madsen and Jonathan Lavoie and Haoyu Qi and Jens Eisert and Dominik Hangleiter and Bill Fefferman and Ish Dhand} } @article {2909, title = {Tight bounds on the convergence of noisy random circuits to uniform}, year = {2021}, month = {12/1/2021}, abstract = {

We study the properties of output distributions of noisy, random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what was thought prior to this work.\ 

}, url = {https://arxiv.org/abs/2112.00716}, author = {Abhinav Deshpande and Bill Fefferman and Alexey V. Gorshkov and Michael Gullans and Pradeep Niroula and Oles Shtanko} } @article {2406, title = {Complexity phase diagram for interacting and long-range bosonic Hamiltonians}, year = {2019}, month = {06/10/2019}, abstract = {

Recent years have witnessed a growing interest in topics at the intersection of many-body physics and complexity theory. Many-body physics aims to understand and classify emergent behavior of systems with a large number of particles, while complexity theory aims to classify computational problems based on how the time required to solve the problem scales as the problem size becomes large. In this work, we use insights from complexity theory to classify phases in interacting many-body systems. Specifically, we demonstrate a \"complexity phase diagram\" for the Bose-Hubbard model with long-range hopping. This shows how the complexity of simulating time evolution varies according to various parameters appearing in the problem, such as the evolution time, the particle density, and the degree of locality. We find that classification of complexity phases is closely related to upper bounds on the spread of quantum correlations, and protocols to transfer quantum information in a controlled manner. Our work motivates future studies of complexity in many-body systems and its interplay with the associated physical phenomena.\ 

}, url = {https://arxiv.org/abs/1906.04178}, author = {Nishad Maskara and Abhinav Deshpande and Minh C. Tran and Adam Ehrenberg and Bill Fefferman and Alexey V. Gorshkov} } @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 {2210, title = {Dynamical phase transitions in sampling complexity}, journal = {Phys. Rev. Lett.}, volume = {121}, year = {2018}, pages = {12 pages, 4 figures. v3: published version}, abstract = {

We make the case for studying the complexity of approximately simulating (sampling) quantum systems for reasons beyond that of quantum computational supremacy, such as diagnosing phase transitions. We consider the sampling complexity as a function of time\ t\ due to evolution generated by spatially local quadratic bosonic Hamiltonians. We obtain an upper bound on the scaling of\ t\ with the number of bosons\ n\ for which approximate sampling is classically efficient. We also obtain a lower bound on the scaling of\ t\ with\ n\ for which any instance of the boson sampling problem reduces to this problem and hence implies that the problem is hard, assuming the conjectures of Aaronson and Arkhipov [Proc. 43rd Annu. ACM Symp. Theory Comput. STOC \&$\#$39;11]. This establishes a dynamical phase transition in sampling complexity. Further, we show that systems in the Anderson-localized phase are always easy to sample from at arbitrarily long times. We view these results in the light of classifying phases of physical systems based on parameters in the Hamiltonian. In doing so, we combine ideas from mathematical physics and computational complexity to gain insight into the behavior of condensed matter, atomic, molecular and optical systems.

}, doi = {https://doi.org/10.1103/PhysRevLett.121.030501}, url = {https://arxiv.org/abs/1703.05332}, author = {Abhinav Deshpande and Bill Fefferman and Minh C. Tran and Michael Foss-Feig and Alexey V. Gorshkov} } @article {2311, title = {Quantum Supremacy and the Complexity of Random Circuit Sampling}, year = {2018}, abstract = {

A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore $\#$P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.\ 

}, url = {https://arxiv.org/abs/1803.04402}, author = {Adam Bouland and Bill Fefferman and Chinmay Nirkhe and Umesh Vazirani} } @article {1952, title = {Complexity of sampling as an order parameter}, year = {2017}, month = {2017/03/15}, abstract = {

We consider the classical complexity of approximately simulating time evolution under spatially local quadratic bosonic Hamiltonians for time\ t. We obtain upper and lower bounds on the scaling of\ twith the number of bosons,\ n, for which simulation, cast as a sampling problem, is classically efficient and provably hard, respectively. We view these results in the light of classifying phases of physical systems based on parameters in the Hamiltonian and conjecture a link to dynamical phase transitions. In doing so, we combine ideas from mathematical physics and computational complexity to gain insight into the behavior of condensed matter systems.

}, url = {https://arxiv.org/abs/1703.05332}, author = {Abhinav Deshpande and Bill Fefferman and Michael Foss-Feig and Alexey V. Gorshkov} } @article {1921, title = {Exact sampling hardness of Ising spin models}, journal = {Physical Review A}, volume = {96}, year = {2017}, month = {2017/09/14}, pages = {032324}, abstract = {

We study the complexity of classically sampling from the output distribution of an Ising spin model, which can be implemented naturally in a variety of atomic, molecular, and optical systems. In particular, we construct a specific example of an Ising Hamiltonian that, after time evolution starting from a trivial initial state, produces a particular output configuration with probability very nearly proportional to the square of the permanent of a matrix with arbitrary integer entries. In a similar spirit to boson sampling, the ability to sample classically from the probability distribution induced by time evolution under this Hamiltonian would imply unlikely complexity theoretic consequences, suggesting that the dynamics of such a spin model cannot be efficiently simulated with a classical computer. Physical Ising spin systems capable of achieving problem-size instances (i.e., qubit numbers) large enough so that classical sampling of the output distribution is classically difficult in practice may be achievable in the near future. Unlike boson sampling, our current results only imply hardness of\ exact\ classical sampling, leaving open the important question of whether a much stronger approximate-sampling hardness result holds in this context. The latter is most likely necessary to enable a convincing experimental demonstration of quantum supremacy. As referenced in a recent paper [A. Bouland, L. Mancinska, and X. Zhang, in\ Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Leibniz International Proceedings in Informatics (Schloss Dagstuhl\–Leibniz-Zentrum f{\"u}r Informatik, Dagstuhl, 2016)], our result completes the sampling hardness classification of two-qubit commuting Hamiltonians.

}, doi = {10.1103/PhysRevA.96.032324}, url = {https://arxiv.org/abs/1701.03167}, author = {Bill Fefferman and Michael Foss-Feig and Alexey V. Gorshkov} } @article {1760, title = {A Complete Characterization of Unitary Quantum Space}, year = {2016}, month = {2016/04/05}, abstract = {We give two complete characterizations of unitary quantum space-bounded classes. The first is based on the Matrix Inversion problem for well-conditioned matrices. We show that given the size-n efficient encoding of a 2O(k(n)){\texttimes}2O(k(n)) well-conditioned matrix H, approximating a particular entry of H-1 is complete for the class of problems solvable by a quantum algorithm that uses O(k(n)) space and performs all quantum measurements at the end of the computation. In particular, the problem of computing entries of H-1 for an explicit well-conditioned n{\texttimes}n matrix H is complete for unitary quantum logspace. We then show that the problem of approximating to high precision the least eigenvalue of a positive semidefinite matrix H, encoded as a circuit, gives a second characterization of unitary quantum space complexity. In the process we also establish an equivalence between unitary quantum space-bounded classes and certain QMA proof systems. As consequences, we establish that QMA with exponentially small completeness-soundness gap is equal to PSPACE, that determining whether a local Hamiltonian is frustration-free is PSPACE-complete, and give a provable setting in which the ability to prepare PEPS states gives less computational power than the ability to prepare the ground state of a generic local Hamiltonian.}, url = {http://arxiv.org/abs/1604.01384}, author = {Bill Fefferman and Cedric Yen-Yu Lin} } @conference {1712, title = {Computational Security of Quantum Encryption}, booktitle = {Computational Security of Quantum Encryption. In: Nascimento A., Barreto P. (eds) Information Theoretic Security. }, year = {2016}, month = {2016/11/10}, abstract = {

Quantum-mechanical devices have the potential to transform cryptography. Most research in this area has focused either on the information-theoretic advantages of quantum protocols or on the security of classical cryptographic schemes against quantum attacks. In this work, we initiate the study of another relevant topic: the encryption of quantum data in the computational setting. In this direction, we establish quantum versions of several fundamental classical results. First, we develop natural definitions for private-key and public-key encryption schemes for quantum data. We then define notions of semantic security and indistinguishability, and, in analogy with the classical work of Goldwasser and Micali, show that these notions are equivalent. Finally, we construct secure quantum encryption schemes from basic primitives. In particular, we show that quantum-secure one-way functions imply IND-CCA1-secure symmetric-key quantum encryption, and that quantum-secure trapdoor one-way permutations imply semantically-secure public-key quantum encryption.

}, url = {https://link.springer.com/chapter/10.1007\%2F978-3-319-49175-2_3}, author = {Gorjan Alagic and Anne Broadbent and Bill Fefferman and Tommaso Gagliardoni and Christian Schaffner and Michael St. Jules} } @article {1704, title = {Quantum Merlin Arthur with Exponentially Small Gap}, year = {2016}, month = {2016/01/08}, abstract = {We study the complexity of QMA proof systems with inverse exponentially small promise gap. We show that this class can be exactly characterized by PSPACE, the class of problems solvable with a polynomial amount of memory. As applications we show that a "precise" version of the Local Hamiltonian problem is PSPACE-complete, and give a provable setting in which the ability to prepare PEPS states is not as powerful as the ability to prepare the ground state of general Local Hamiltonians.}, url = {http://arxiv.org/abs/1601.01975}, author = {Bill Fefferman and Cedric Yen-Yu Lin} } @article {1713, title = {On Quantum Obfuscation}, year = {2016}, month = {2016/02/04}, abstract = {Encryption of data is fundamental to secure communication in the modern world. Beyond encryption of data lies obfuscation, i.e., encryption of functionality. It is well-known that the most powerful means of obfuscating classical programs, so-called {\textquoteleft}{\textquoteleft}black-box obfuscation{\textquoteright},{\textquoteright} is provably impossible [Barak et al {\textquoteright}12]. However, several recent results have yielded candidate schemes that satisfy a definition weaker than black-box, and yet still have numerous applications. In this work, we initialize the rigorous study of obfuscating programs via quantum-mechanical means. We define notions of quantum obfuscation which encompass several natural variants. The input to the obfuscator can describe classical or quantum functionality, and the output can be a circuit description or a quantum state. The obfuscator can also satisfy one of a number of obfuscation conditions: black-box, information-theoretic black-box, indistinguishability, and best possible; the last two conditions come in three variants: perfect, statistical, and computational. We discuss many applications, including CPA-secure quantum encryption, quantum fully-homomorphic encryption, and public-key quantum money. We then prove several impossibility results, extending a number of foundational papers on classical obfuscation to the quantum setting. We prove that quantum black-box obfuscation is impossible in a setting where adversaries can possess more than one output of the obfuscator. In particular, generic transformation of quantum circuits into black-box-obfuscated quantum circuits is impossible. We also show that statistical indistinguishability obfuscation is impossible, up to an unlikely complexity-theoretic collapse. Our proofs involve a new tool: chosen-ciphertext-secure encryption of quantum data, which was recently shown to be possible assuming quantum-secure one-way functions exist [Alagic et al {\textquoteright}16].}, url = {http://arxiv.org/abs/1602.01771}, author = {Gorjan Alagic and Bill Fefferman} } @article {1818, title = {Space-Efficient Error Reduction for Unitary Quantum Computations}, journal = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, volume = {55}, year = {2016}, month = {2016/04/27}, pages = {14:1--14:14}, abstract = {

This paper develops general space-efficient methods for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness\ c\ and soundnesss, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most\ 2\−p, the most space-efficient method known requires extra workspace of\ O(plog1c\−s)\ qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper presents error-reduction methods for unitary quantum computations (i.e., computations without intermediate measurements) that require extra workspace of just\ O(logpc\−s)\ qubits. This in particular gives the first methods of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.

}, isbn = {978-3-95977-013-2}, issn = {1868-8969}, doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.14}, url = {http://drops.dagstuhl.de/opus/volltexte/2016/6297}, author = {Bill Fefferman and Hirotada Kobayashi and Cedric Yen-Yu Lin and Tomoyuki Morimae and Harumichi Nishimura} } @article {1464, title = {The Power of Quantum Fourier Sampling}, year = {2015}, month = {2015/07/20}, abstract = { A line of work initiated by Terhal and DiVincenzo and Bremner, Jozsa, and Shepherd, shows that quantum computers can efficiently sample from probability distributions that cannot be exactly sampled efficiently on a classical computer, unless the PH collapses. Aaronson and Arkhipov take this further by considering a distribution that can be sampled efficiently by linear optical quantum computation, that under two feasible conjectures, cannot even be approximately sampled classically within bounded total variation distance, unless the PH collapses. In this work we use Quantum Fourier Sampling to construct a class of distributions that can be sampled by a quantum computer. We then argue that these distributions cannot be approximately sampled classically, unless the PH collapses, under variants of the Aaronson and Arkhipov conjectures. In particular, we show a general class of quantumly sampleable distributions each of which is based on an "Efficiently Specifiable" polynomial, for which a classical approximate sampler implies an average-case approximation. This class of polynomials contains the Permanent but also includes, for example, the Hamiltonian Cycle polynomial, and many other familiar $\#$P-hard polynomials. Although our construction, unlike that proposed by Aaronson and Arkhipov, likely requires a universal quantum computer, we are able to use this additional power to weaken the conjectures needed to prove approximate sampling hardness results. }, url = {http://arxiv.org/abs/1507.05592v1}, author = {Bill Fefferman and Chris Umans} } @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 {1549, title = {On Beating the Hybrid Argument}, journal = {Proceedings, ITCS}, volume = {9}, year = {2012}, month = {2013/11/14}, pages = {809-843}, abstract = {The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor k equal to the bit-length of the distributions: -distinguishability implies only /k-predictability. This paper studies the consequences of avoiding this loss {\textendash} what we call {\textquotedblleft}beating the hybrid argument{\textquotedblright} {\textendash} and develops new proof techniques that circumvent the loss in certain natural settings. Specifically, we obtain the following results: 1. We give an instantiation of the Nisan-Wigderson generator (JCSS {\textquoteright}94) that can be broken by quantum computers, and that is o(1)-unpredictable against AC0 . This is not enough to imply indistinguishability via the hybrid argument because of the hybrid-argument loss; nevertheless, we conjecture that this generator indeed fools AC0 , and we prove this statement for a simplified version of the problem. Our conjecture implies the existence of an oracle relative to which BQP is not in the PH, a longstanding open problem. 2. We show that the {\textquotedblleft}INW{\textquotedblright} generator by Impagliazzo, Nisan, and Wigderson (STOC {\textquoteright}94) with seed length O(log n log log n) produces a distribution that is 1/ log n-unpredictable against poly-logarithmic width (general) read-once oblivious branching programs. Thus avoiding the hybrid-argument loss would lead to a breakthrough in generators against small space. 3. We study pseudorandom generators obtained from a hard function by repeated sampling. We identify a property of functions, {\textquotedblleft}resamplability,{\textquotedblright} that allows us to beat the hybrid argument, leading to new pseudorandom generators for AC0 [p] and similar classes. Although the generators have sub-linear stretch, they represent the best-known generators for these classes. Thus we establish that {\textquotedblleft}beating{\textquotedblright} or bypassing the hybrid argument would have two significant consequences in complexity, and we take steps toward that goal by developing techniques that indeed beat the hybrid argument in related (but simpler) settings, leading to best-known PRGs for certain complexity classes. }, url = {http://users.cms.caltech.edu/~umans/papers/FSUV10.pdf}, author = {Bill Fefferman and Ronen Shaltiel and Christopher Umans and Emanuele Viola} } @article {1463, title = {Pseudorandom generators and the BQP vs. PH problem}, year = {2010}, month = {2010/07/02}, abstract = { It is a longstanding open problem to devise an oracle relative to which BQP does not lie in the Polynomial-Time Hierarchy (PH). We advance a natural conjecture about the capacity of the Nisan-Wigderson pseudorandom generator [NW94] to fool AC_0, with MAJORITY as its hard function. Our conjecture is essentially that the loss due to the hybrid argument (which is a component of the standard proof from [NW94]) can be avoided in this setting. This is a question that has been asked previously in the pseudorandomness literature [BSW03]. We then make three main contributions: (1) We show that our conjecture implies the existence of an oracle relative to which BQP is not in the PH. This entails giving an explicit construction of unitary matrices, realizable by small quantum circuits, whose row-supports are "nearly-disjoint." (2) We give a simple framework (generalizing the setting of Aaronson [A10]) in which any efficiently quantumly computable unitary gives rise to a distribution that can be distinguished from the uniform distribution by an efficient quantum algorithm. When applied to the unitaries we construct, this framework yields a problem that can be solved quantumly, and which forms the basis for the desired oracle. (3) We prove that Aaronson{\textquoteright}s "GLN conjecture" [A10] implies our conjecture; our conjecture is thus formally easier to prove. The GLN conjecture was recently proved false for depth greater than 2 [A10a], but it remains open for depth 2. If true, the depth-2 version of either conjecture would imply an oracle relative to which BQP is not in AM, which is itself an outstanding open problem. Taken together, our results have the following interesting interpretation: they give an instantiation of the Nisan-Wigderson generator that can be broken by quantum computers, but not by the relevant modes of classical computation, if our conjecture is true. }, url = {http://arxiv.org/abs/1007.0305v3}, author = {Bill Fefferman and Christopher Umans} } @article {1465, title = {The Power of Unentanglement}, year = {2008}, month = {2008/04/04}, abstract = { The class QMA(k), introduced by Kobayashi et al., consists of all languages that can be verified using k unentangled quantum proofs. Many of the simplest questions about this class have remained embarrassingly open: for example, can we give any evidence that k quantum proofs are more powerful than one? Does QMA(k)=QMA(2) for k>=2? Can QMA(k) protocols be amplified to exponentially small error? In this paper, we make progress on all of the above questions. First, we give a protocol by which a verifier can be convinced that a 3SAT formula of size n is satisfiable, with constant soundness, given ~O(sqrt(n)) unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on the existence of very short PCPs. Second, we show that assuming a weak version of the Additivity Conjecture from quantum information theory, any QMA(2) protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for all k>=2. Third, we prove the nonexistence of "perfect disentanglers" for simulating multiple Merlins with one. }, url = {http://arxiv.org/abs/0804.0802v2}, author = {Scott Aaronson and Salman Beigi and Andrew Drucker and Bill Fefferman and Peter Shor} }