%% Theory of Computing
%% File: v009a004.bib
%% Publication date: February 9, 2013
%% Authors: Scott Aaronson and Alex Arkhipov
@string{acm      = "ACM Press"}
@string{ieee     = "IEEE Comp. Soc. Press"}
@string{springer = "Springer"}

@string{JACM="J. ACM"}
@string{SIAMJComput="SIAM J. Comput."}
@string{tcs      = "Theoret. Comput. Sci."}

@string{ipl      = "Inform. Process. Lett."}
@string{jcss="J. Comput. System Sci."}
@string{SIAMJDiscreteMath="SIAM J. Discrete Math."}
%
@string{PhysRevA="Phys. Rev. A"}
@string{PhysRevLett="Phys. Rev. Lett."}
@string{qic="Quantum Information {\&} Computation"}
@string{rsl="Proc. Roy. Soc. A"}

@string{stoc83="Proc. 15th STOC"}
@string{stoc91="Proc. 23rd STOC"}
@string{stoc92="Proc. 24th STOC"}
@string{stoc97="Proc. 29th STOC"}
@string{stoc01="Proc. 33rd STOC"}
@string{stoc06="Proc. 38th STOC"}
@string{stoc10="Proc. 42nd STOC"}


@string{focs89="Proc. 30th FOCS"}
@string{focs96="Proc. 37th FOCS"}
@string{focs99="Proc. 40th FOCS"}
@string{focs00="Proc. 41st FOCS"}

@string{ccc=" IEEE Conf. on Computational Complexity"}
@string{ccc98="Proc. 13th" # ccc # " (CCC'98)"}
@string{ccc10="Proc. 25th" # ccc # " (CCC'10)"}

@string{stacs=" Symp. Theoretical Aspects of Comp. Sci."}
@string{stacs99= "Proc. 16th" # stacs  # " (STACS'99)"}

@string{random=" Internat. Workshop on Randomization and Computation"}
@string{random12= "Proc.  16th" # random  # " (RANDOM'12)"}

@inproceedings{gurvits:alg,
title = {On the Complexity of Mixed Discriminants and Related Problems},
author = {Leonid Gurvits},
booktitle = {30th Internat. Symp. Mathematical Foundations of Computer Science (MFCS'05)},
publisher = springer,
year = {2005},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {447-458},
doi = {10.1007/11549345\_39},
}


@article{shor,
title = {Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer},
author = {Peter W. Shor},
journal = SIAMJComput,
number = {5},
volume = {26},
year = {1997},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1484-1509},
doi = {10.1137/S0097539795293172},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.1994.365700}{FOCS'94}. Preprint at \href{http://arxiv.org/abs/quant-ph/9508027}{arXiv}}
}
%
@inproceedings{shor-conference,
  author    = {Peter W. Shor},
  title     = {Algorithms for Quantum Computation: Discrete Logarithms and Factoring},
  booktitle = {FOCS},
  year      = {1994},
  pages     = {124-134},
  doi       = {10.1109/SFCS.1994.365700},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
%
%
@article{ab,
title = {Fault-Tolerant Quantum Computation with Constant Error Rate},
author = {Dorit Aharonov and Michael Ben-Or},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/258533.258579}{STOC'97}. Preprint at \href{http://arxiv.org/abs/quant-ph/9906129}{arXiv}},
journal = SIAMJComput,
number = {4},
volume = {38},
year = {2008},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1207-1282},
doi = {10.1137/S0097539799359385},
}

@inproceedings{ab-original,
title = {Fault-Tolerant Quantum Computation With Constant Error},
author = {Dorit Aharonov and Michael Ben-Or},
crossref = {pstoc97},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {176-188},
doi = {10.1145/258533.258579},
}


@article{valiant,
title = {The Complexity of Computing the Permanent},
author = {Leslie G. Valiant},
journal = tcs,
number = {2},
volume = {8},
year = {1979},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {189-201},
doi = {10.1016/0304-3975(79)90044-6},
}
%
@article{ag,
title = {Improved simulation of stabilizer circuits},
author = {Scott Aaronson and Daniel Gottesman},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0406196}{arXiv}},
journal = PhysRevA,
pages = {052328},
number = {5},
volume = {70},
year = {2004},
doi = {10.1103/PhysRevA.70.052328},
}
%
@article{caianiello,
title = {On quantum field theory, {I}: explicit solution of {D}yson's equation in electrodynamics without use of {F}eynman graphs},
author = {Eduardo R. Caianiello},
journal = {Nuovo Cimento},
number = {12},
volume = {10},
year = {1953},
pages = {1634-1652},
doi = {10.1007/BF02781659},
}
%
@article{lounis,
title = {Single-photon sources},
author = {Brahim Lounis and Michel Orrit},
journal = {Reports on Progress in Physics},
pages = {1129-1179},
number = {5},
volume = {68},
year = {2005},
doi = {10.1088/0034-4885/68/5/R04},
}
%
%
@incollection{godsilgutman,
title = {On the matching polynomial of a graph},
author = {Chris D. Godsil and Ivan Gutman},
publisher = {North Holland},
booktitle = {Algebraic Methods in Graph Theory I},
year = {1981},
pages = {241-249},
}
%
﻿@article {godsilgutman-journal,
author = {Chris D. Godsil and Ivan Gutman},
title = {On the theory of the matching polynomial},
journal = {J. Graph Theory},
volume = {5},
number = {2},
doi = {10.1002/jgt.3190050203},
pages = {137--144},
year = {1981},
}
%
@article{fr,
title = {Complexity Limitations on Quantum Computation},
author = {Lance Fortnow and John D. Rogers},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/CCC.1998.694606}{CCC'98}. Preprint at \href{http://arxiv.org/abs/cs.CC/9811023}{arXiv}},
journal = jcss,
number = {2},
volume = {59},
year = {1999},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {240-252},
doi = {10.1006/jcss.1999.1651},
}
%
@inproceedings{fr-conference,
title = {Complexity Limitations on Quantum Computation},
author = {Lance Fortnow and John D. Rogers},
booktitle = ccc98,
publisher = ieee,
year = {1998},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {202-209},
doi = {10.1109/CCC.1998.694606},
}
%
@phdthesis{reffy,
title = {Asymptotics of random unitaries},
author = {J\'{u}lia R\'{e}ffy},
school = {Budapest University of Technology and Economics},
note = {\url{http://www.math.bme.hu/~reffyj/disszer.pdf}},
year = {2005},
}

@article{aar:bf,
title = {Algorithms for {B}oolean Function Query Properties},
author = {Scott Aaronson},
journal = SIAMJComput,
number = {5},
volume = {32},
year = {2003},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1140-1157},
doi = {10.1137/S0097539700379644},
}
%
@unpublished{ebs:tillmann,
title = {Experimental boson sampling},
author = {Max Tillmann and Borivoje Daki\'{c} and Ren\'{e} Heilmann and Stefan Nolte and Alexander Szameit and Philip Walther},
eprint = {arxiv:1212.2240},
year = {2012},
}
%
@article{toda,
title = {{PP} is as Hard as the Polynomial-Time Hierarchy},
author = {Seinosuke Toda},
journal = SIAMJComput,
number = {5},
volume = {20},
year = {1991},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {865-877},
doi = {10.1137/0220053},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.1989.63527}{FOCS'89}}
}
%
@article{toda-conference,
author = {Seinosuke Toda},
title = {On the computational power of {PP} and $\oplus$P},
crossref = {pfocs89},
pages = {514-519},
doi = {10.1109/SFCS.1989.63527},
publisher = ieee,
}
%
@article{bjs,
title = {Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy},
author = {Michael J. Bremner and Richard Jozsa and Dan J. Shepherd},
note = {Preprint at \href{http://arxiv.org/abs/1005.1407}{arXiv}},
journal = rsl,
number = {2126},
volume = {467},
year = {2011},
pages = {459-472},
doi = {10.1098/rspa.2010.0301},
}

@inproceedings{bcwz,
title = {Bounds for Small-Error and Zero-Error Quantum Algorithms},
author = {Harry Buhrman and Richard Cleve and Ronald de Wolf and Christof Zalka},
crossref = {pfocs99},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {358-368},
doi = {10.1109/SFFCS.1999.814607},
note = {Preprint at \href{http://arxiv.org/abs/cs.CC/9904019}{arXiv}}
}


@inproceedings{aar:samp,
title = {The Equivalence of Sampling and Searching},
author = {Scott Aaronson},
booktitle = {6th Internat. Comp. Sci. Symp. in Russia (CSR'11)},
publisher = springer,
year = {2011},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1-14},
doi = {10.1007/978-3-642-20712-9\_1},
note = {Available at \href{http://eccc.hpi-web.de/report/2010/128/}{ECCC}. Preprint at \href{http://arxiv.org/abs/1009.5104}{arXiv}},
}

@article{egorychev,
title = {Proof of the van der {W}aerden conjecture for permanents},
author = {Georgy P. Egorychev},
note = {English translation in Siberian Math. J. 22 (6), pp. 854-859, 1981},
journal = {Sibirsk. Mat. Zh.},
number = {6},
volume = {22},
year = {1981},
pages = {65-71},
doi = {10.1007/BF00968054},
}
%
@unpublished{ebs:crespi,
title = {Experimental boson sampling in arbitrary integrated photonic circuits},
author = {Andrea Crespi and Roberto Osellame and Roberta Ramponi and Daniel J. Brod and Ernesto F. Galv{\~{a}}o and Nicol\`{o} Spagnolo and Chiara Vitelli and Enrico Maiorino and Paolo Mataloni and Fabio Sciarrino},
eprint = {arxiv:1212.2783},
year = {2012},
}

@inproceedings{cw,
title = {Fast parallel circuits for the quantum {F}ourier transform},
author = {Richard Cleve and John Watrous},
crossref = {pfocs00},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {526-536},
doi = {10.1109/SFCS.2000.892140},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0006004}{arXiv}},
}


@article{cv,
title = {Concentration of Random Determinants and Permanent Estimators},
author = {Kevin P. Costello and Van H. Vu},
note = {Preprint at \href{http://arxiv.org/abs/0905.1909}{arXiv}},
journal = SIAMJDiscreteMath,
number = {3},
volume = {23},
year = {2009},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1356-1371},
doi = {10.1137/080733784},
}


@article{ceperley,
title = {An overview of quantum {M}onte {C}arlo methods},
author = {David M. Ceperley},
journal = {Reviews in Mineralogy and Geochemistry},
number = {1},
volume = {71},
year = {2010},
pages = {129-135},
doi = {10.2138/rmg.2010.71.6}
}
%
%
@article{simon,
title = {On the Power of Quantum Computation},
author = {Daniel R. Simon},
note = {Preliminary version in \href{http://dx.doi.org/10.1109/SFCS.1994.365701}{FOCS'94}},
journal = SIAMJComput,
number = {5},
volume = {26},
year = {1997},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1474-1483},
doi = {10.1137/S0097539796298637},
}

@inproceedings{simon-original,
title = {On the power of quantum computation},
author = {Daniel R. Simon},
crossref = {pfocs94},
pages = {116-123},
doi = {10.1109/SFCS.1994.365701},
} 
%
@inproceedings{aar:ph,
title = {{BQP} and the polynomial hierarchy},
author = {Scott Aaronson},
crossref = {pstoc10},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {141-150},
doi = {10.1145/1806689.1806711},
note = {Preprint at \href{http://arxiv.org/abs/0910.4698}{arXiv}},
}
%
@article{gkp,
title = {Encoding a qubit in an oscillator},
author = {Daniel Gottesman and Alexei Kitaev and John Preskill},
journal = PhysRevA,
pages = {012310},
volume = {64},
number = {1},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0008040}{arXiv}},
year = {2001},
doi = {10.1103/PhysRevA.64.012310},
}

@unpublished{scheel,
title = {Permanents in linear optical networks},
author = {Stefan Scheel},
eprint = {arxiv:quant-ph/0406127},
year = {2004},
}
%
@article{hht,
title = {Threshold Computation and Cryptographic Security},
author = {Yenjo Han and Lane A. Hemaspaandra and Thomas Thierauf},
note = {Preliminary version in \href{http://dx.doi.org/10.1007/3-540-57568-5_253}{ISAAC'93}},
journal = SIAMJComput,
number = {1},
volume = {26},
year = {1997},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {59-78},
doi = {10.1137/S0097539792240467},
}
%
@inproceedings{hht-conference,
title = {Threshold Computation and Cryptographic Security},
author = {Yenjo Han and Lane A. Hemaspaandra and Thomas Thierauf},
booktitle = {4th Internat. Symp. Algorithms and Computation (ISAAC'93)},
publisher = springer,
year = {1993},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {230-239},
doi = {10.1007/3-540-57568-5\_253},
}
%
@article{al:fermi,
title = {Simulation of many-body {F}ermi systems on a universal quantum computer},
author = {Daniel S. Abrams and Seth Lloyd},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/9703054}{arXiv}},
journal = PhysRevLett,
number = {13},
volume = {79},
year = {1997},
pages = {2586-2589},
doi = {10.1103/PhysRevLett.79.2586},
}
%
@article{rudolph,
title = {A simple encoding of a quantum circuit amplitude as a matrix permanent},
author = {Terry Rudolph},
journal = PhysRevA,
volume = {80},
number = {5},
eprint = {arxiv:0909.3005},
year = {2009},
doi = {10.1103/PhysRevA.80.054302},
}
%
@unpublished{rudolph-arxiv,
title = {A simple encoding of a quantum circuit amplitude as a matrix permanent},
author = {Terry Rudolph},
eprint = {arxiv:0909.3005},
year = {2009},
}
%
@article{aar:pp,
title = {Quantum computing, postselection, and probabilistic polynomial-time},
author = {Scott Aaronson},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0412187}{arXiv}},
journal = rsl,
number = {2063},
volume = {461},
year = {2005},
pages = {3473-3482},
doi = {10.1098/rspa.2005.1546},
}
%
@article{fghp,
title = {Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy},
author = {Stephen Fenner and Frederic Green and Steven Homer and Randall Pruim},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/9812056}{arXiv}},
journal = rsl,
number = {1991},
volume = {455},
year = {1999},
pages = {3953-3966},
doi = {10.1098/rspa.1999.0485},
} 
@article{taovu:perm,
title = {On the permanent of random {B}ernoulli matrices},
author = {Terence Tao and Van H. Vu},
note = {Preprint at \href{http://arxiv.org/abs/0804.2362}{arXiv}},
journal = {Advances in Mathematics},
number = {3},
volume = {220},
year = {2009},
pages = {657-669},
doi = {10.1016/j.aim.2008.09.006},
}
%
@unpublished{feffumans,
title = {Pseudorandom generators and the {BQP} vs. {PH} problem},
author = {Bill Fefferman and Chris Umans},
eprint = {arxiv:1007.0305},
year = {2010},
}

@article{knilaflamme,
title = {Power of one bit of quantum information},
author = {Emanuel Knill and Raymond Laflamme},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/9802037}{arXiv}},
journal = PhysRevLett,
number = {25},
volume = {81},
year = {1998},
pages = {5672-5675},
doi = {10.1103/PhysRevLett.81.5672},
}
%
@article{td,
title = {Adaptive quantum computation, constant-depth quantum circuits and {A}rthur-{M}erlin games},
author = {Barbara M. Terhal and David P. DiVincenzo},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0205133}{arXiv}},
journal = qic,
number = {2},
volume = {4},
year = {2004},
pages = {134-145},
eprint = {acm:2011582}
}
%
@article{petzreffy,
title = {On asymptotics of large {H}aar distributed unitary matrices},
author = {D\'{e}nes Petz and J\'{u}lia R\'{e}ffy},
note = {Preprint at \href{http://arxiv.org/abs/math/0310338}{arXiv}},
journal = {Periodica Mathematica Hungarica},
number = {1},
volume = {49},
year = {2004},
pages = {103-117},
doi = {10.1023/B:MAHU.0000040542.56072.ab},
}
%
@incollection{lipton,
title = {New directions in testing},
author = {Richard J. Lipton},
publisher = {AMS},
booktitle = {Distributed Computing and Cryptography},
year = {1991},
pages = {191-202},
}
%
@article{jsv,
title = {A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries},
author = {Mark Jerrum and Alistair Sinclair and Eric Vigoda},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/380752.380877}{STOC'01}},
journal = JACM,
number = {4},
volume = {51},
year = {2004},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {671-697},
doi = {10.1145/1008731.1008738},
}
%
@inproceedings{jsv-conference,
title = {A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries},
author = {Mark Jerrum and Alistair Sinclair and Eric Vigoda},
crossref = {pstoc01},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {712-721},
doi = {10.1145/380752.380877},
}
%
@article{shepherd,
title = {Temporally unstructured quantum computation},
author = {Dan Shepherd and Michael J. Bremner},
note = {Preprint at \href{http://arxiv.org/abs/0809.0847}{arXiv}},
journal = rsl,
number = {2105},
volume = {465},
year = {2009},
pages = {1413-1439},
doi = {10.1098/rspa.2008.0443},
}

@article{feynman:qc,
title = {Simulating physics with computers},
author = {Richard P. Feynman},
journal = {Int. J. Theoretical Physics},
number = {6-7},
volume = {21},
year = {1982},
pages = {467-488},
doi = {10.1007/BF02650179}
} 
%
@article{mastrodon,
title = {Elementary proof for asymptotics of large {H}aar-distributed unitary matrices},
author = {Christian Mastrodonato and Roderich Tumulka},
note = {Preprint at \href{http://arxiv.org/abs/0705.3146}{arXiv}},
journal = {Letters in Mathematical Physics},
number = {1},
volume = {82},
year = {2007},
pages = {51-59},
doi = {10.1007/s11005-007-0194-7},
}
%
@article{bdek,
title = {Charge detection enables free-electron quantum computation},
author = {Carlo W. J. Beenakker and David P. DiVincenzo and Clive Emary and Marco Kindermann},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0401066}{arXiv}},
journal = PhysRevLett,
pages = {020501},
number = {2},
volume = {93},
year = {2004},
doi = {10.1103/PhysRevLett.93.020501},
}
%
@article{girko,
title = {A refinement of the {C}entral {L}imit {T}heorem for random determinants},
author = {Viacheslav L. Girko},
note = {Translation in Theory Probab. Appl 42 (1) (1998), 121-129},
journal = {Teor. Veroyatnost. i Primenen},
number = {1},
volume = {42},
year = {1997},
pages = {63-73},
doi = {10.1137/S0040585X97975939},
}
%
@book{lange,
title = {Applied Probability},
author = {Kenneth Lange},
publisher = springer,
year = {2003},
}

@inproceedings{khot,
title = {On the {U}nique {G}ames {C}onjecture},
author = {Subhash Khot},
booktitle = ccc10,
publisher = ieee,
year = {2010},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {99-121},
doi = {10.1109/CCC.2010.19},
}
%
@book{nc,
title = {Quantum Computation and Quantum Information},
author = {Michael A. Nielsen and Isaac L. Chuang},
publisher = {Cambridge University Press},
year = {2000},
} 
%
@article{stockmeyer,
author = {Larry J. Stockmeyer},
title = {On Approximation Algorithms for \#{P}},
journal = SIAMJComput,
volume = {14},
number = {4},
pages = {849-861},
year = {1985},
doi = {10.1137/0214060},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/800061.808740}{STOC'83}}
}


@inproceedings{stockmeyer-original,
title = {The Complexity of Approximate Counting},
author = {Larry J. Stockmeyer},
crossref = {pstoc83},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {118-126},
doi = {10.1145/800061.808740},
}
%
@article{falikman,
title = {Proof of the van der {W}aerden conjecture regarding the permanent of a doubly stochastic matrix},
author = {Dmitry I. Falikman},
note = {English translation in Math. Notes 29 (6), pp. 475-479, 1981},
journal = {Mat. Zametki},
number = {6},
volume = {29},
year = {1981},
pages = {931-938},
doi = {10.1007/BF01163285},
}
%
@article{dgp,
title = {The complexity of computing a {N}ash equilibrium},
author = {Constantinos Daskalakis and Paul W. Goldberg and Christos H. Papadimitriou},
journal = {Commun. ACM},
number = {2},
volume = {52},
year = {2009},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {89-97},
doi = {10.1145/1461928.1461951},
}
%
@inproceedings{dgp-conference,
title = {The complexity of computing a {N}ash equilibrium},
author = {Constantinos Daskalakis and Paul W. Goldberg and Christos H. Papadimitriou},
crossref = {pstoc06},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {71-78},
doi = {10.1145/1132516.1132527},
}
%
@article{dgp-sicomp,
title = {The Complexity of Computing a {N}ash Equilibrium},
author = {Constantinos Daskalakis and Paul W. Goldberg and Christos H. Papadimitriou},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/1132516.1132527}{STOC'06}},
journal = {SIAM J. Comput.},
number = {1},
volume = {39},
year = {2009},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {195-259},
doi = {10.1137/070699652},
}
%
@article{petzreffy2,
title = {Large deviation theorem for the empirical eigenvalue distribution of truncated {H}aar unitary matrices},
author = {D\'{e}n\'{e}s Petz and J\'{u}lia R\'{e}ffy},
note = {Preprint at \href{http://arxiv.org/abs/math/0409552}{arXiv}},
journal = {Prob. Theory and Related Fields},
number = {2},
volume = {133},
year = {2005},
pages = {175-189},
doi = {10.1007/s00440-004-0420-5},
}
%
@article{jordan,
title = {Permutational quantum computing},
author = {Stephen P. Jordan},
note = {Preprint at \href{http://arxiv.org/abs/0906.2508}{arXiv}},
journal = qic,
number = {5},
volume = {10},
year = {2010},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {470-497},
eprint = {acm:2011369}
}

@article{valiant:qc,
title = {Quantum Circuits That Can Be Simulated Classically in Polynomial Time},
author = {Leslie G. Valiant},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/380752.380785}{STOC'01}},
journal = SIAMJComput,
number = {4},
volume = {31},
year = {2002},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1229-1254},
doi = {10.1137/S0097539700377025},
}
%
@inproceedings{valiant:qc-conference,
title = {Quantum computers that can be simulated classically in polynomial time},
author = {Leslie G. Valiant},
crossref = {pstoc01},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {114-123},
doi = {10.1145/380752.380785},
}
%
@article{bartlettsanders,
title = {Requirement for quantum computation},
author = {Stephen D. Bartlett and Barry C. Sanders},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0302125}{arXiv}},
journal = {J. Modern Optics},
number = {15-17},
volume = {50},
year = {2003},
pages = {2331-2340},
doi = {10.1080/09500340308233564},
}
%
@article{ebs:spring,
title = {Boson sampling on a photonic chip},
author = {Justin B. Spring and Benjamin J. Metcalf and Peter C. Humphreys and W. Steven Kolthammer and Xian-Min Jin and Marco Barbieri and Animesh Datta and Nicholas Thomas-Peter and Nathan K. Langford and Dmytro Kundys and James C. Gates and Brian J. Smith and Peter G. R. Smith and Ian A. Walmsley},
journal = {Science},
doi = {10.1126/science.1231692},
note = {Preprint at \href{http://arxiv.org/abs/1212.2622}{arXiv}},
year = {2012 (online)},
}
%
@article{td:fermion,
title = {Classical simulation of noninteracting-fermion quantum circuits},
author = {Barbara M. Terhal and David P. DiVincenzo},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0108010}{arXiv}},
journal = PhysRevA,
pages = {032325},
number = {3},
volume = {65},
year = {2002},
doi = {10.1103/PhysRevA.65.032325},
}

@article{rzbb,
title = {Experimental realization of any discrete unitary operator},
author = {Michael Reck and Anton Zeilinger and Herbert J. Bernstein and Philip Bertani},
journal = PhysRevLett,
number = {1},
volume = {73},
year = {1994},
pages = {58-61},
doi = {10.1103/PhysRevLett.73.58},
}
%
@article{gemmellsudan,
title = {Highly resilient correctors for polynomials},
author = {Peter Gemmell and Madhu Sudan},
journal = ipl,
number = {4},
volume = {43},
year = {1992},
pages = {169-174},
doi = {10.1016/0020-0190(92)90195-2},
}
%
@article{vsbysc,
title = {Experimental realization of {S}hor's quantum factoring algorithm using nuclear magnetic resonance},
author = {Lieven M. K. Vandersypen and Matthias Steffen and Gregory Breyta and Costantino S. Yannoni and Mark H. Sherwood and Isaac L. Chuang},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0112176}{arXiv}},
journal = {Nature},
number = {6866},
volume = {414},
year = {2001},
pages = {883-887},
doi = {10.1038/414883a},
}

@article{jiang,
title = {How many entries of a typical orthogonal matrix can be approximated by independent normals?},
author = {Tiefeng Jiang},
journal = {Ann. Probab.},
number = {4},
volume = {34},
year = {2006},
pages = {1497-1529},
doi = {10.1214/009117906000000205},
}

@article{klm,
title = {A scheme for efficient quantum computation with linear optics},
author = {Emanuel Knill and Raymond Laflamme and Gerard J. Milburn},
note = {See also \href{http://arxiv.org/abs/quant-ph/0006088}{arXiv:quant-ph/0006088}},
journal = {Nature},
volume = {409},
year = {2001},
number = {6816},
pages = {46-52},
doi = {10.1038/35051009},
}
%
@inproceedings{troyanskytishby,
title = {Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix},
author = {Lidror Troyansky and Naftali Tishby},
booktitle = {Proc. 4th Workshop on Physics and Computation (PhysComp'96)},
year = {1996},
note = {Available \href{http://www.cs.huji.ac.il/labs/learning/Papers/perm.pdf}{here}},
}
%
@unpublished{knill:matchgate,
title = {Fermionic linear optics and matchgates},
author = {Emanuel Knill},
eprint = {arxiv:quant-ph/0108033},
year = {2001},
}
%
@article{shi:gate,
title = {Both {T}offoli and controlled-{NOT} need little help to do universal quantum computing},
author = {Yaoyun Shi},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0205115}{arXiv}},
journal = qic,
number = {1},
volume = {3},
year = {2003},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {84-92},
eprint = {acm:2011515}
}


@article{bv,
title = {Quantum Complexity Theory},
author = {Ethan Bernstein and Umesh Vazirani},
note = {Preliminary version in \href{http://dx.doi.org/10.1145/167088.167097}{STOC'93}},
journal = SIAMJComput,
number = {5},
volume = {26},
year = {1997},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {1411-1473},
doi = {10.1137/S0097539796300921},
}
%
@inproceedings{bv-conference,
title = {Quantum complexity theory},
author = {Ethan Bernstein and Umesh V. Vazirani},
crossref = {pstoc93},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {11-20},
doi = {10.1145/167088.167097},
}
%
@inproceedings{sudan,
title = {Maximum Likelihood Decoding of {R}eed {S}olomon Codes},
author = {Madhu Sudan},
crossref = {pfocs96},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {164-172},
doi = {10.1109/SFCS.1996.548475},
}
@article{hom,
title = {Measurement of subpicosecond time intervals between two photons by interference},
author = {C. K. Hong and Zhe-Yu Ou and Leonard Mandel},
journal = PhysRevLett,
number = {18},
volume = {59},
year = {1987},
pages = {2044-2046},
doi = {10.1103/PhysRevLett.59.2044},
}
%
@article{limbeige,
title = {Generalized {H}ong-{O}u-{M}andel experiments with bosons and fermions},
author = {Yuan Liang Lim and Almut Beige},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/0505034}{arXiv}},
journal = {New J. Phys.},
pages = {1-10},
number = {155},
volume = {7},
year = {2005},
doi = {10.1088/1367-2630/7/1/155},
}
%
@book{hastad:book,
title = {Computational Limitations for Small Depth Circuits},
author = {H{\aa}stad, Johan},
publisher = {MIT Press},
year = {1987},
}

@inproceedings{paturi,
title = {On the Degree of Polynomials that Approximate Symmetric {B}oolean Functions},
author = {Ramamohan Paturi},
crossref = {pstoc92},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {468-474},
doi = {10.1145/129712.129758},
}


@inproceedings{glrsw,
title = {Self-Testing/Correcting for Polynomials and for Approximate Functions},
author = {Peter Gemmell and Richard J. Lipton and Ronitt Rubinfeld and Madhu Sudan and Avi Wigderson},
crossref = {pstoc91},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {33-42},
doi = {10.1145/103418.103429},
}


@inproceedings{cps,
title = {On the Hardness of Permanent},
author = {Jin-yi Cai and Aduri Pavan and D. Sivakumar},
booktitle = stacs99,
year = {1999},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {90-99},
doi = {10.1007/3-540-49116-3\_8},
}
%
@article{ebs:broome,
title = {Photonic boson sampling in a tunable circuit},
author = {Matthew A. Broome and Alessandro Fedrizzi and Saleh Rahimi-Keshari and Justin Dove and Scott Aaronson and Timothy C. Ralph and Andrew G. White},
journal = {Science},
doi = {10.1126/science.1231440},
note = {Preprint at \href{http://arxiv.org/abs/1212.2234}{arXiv}},
year = {2012 (online)},
}
%
%
@inproceedings{abms,
title = {Testing Permanent Oracles - Revisited},
author = {Sanjeev Arora and Arnab Bhattacharyya and Rajsekar Manokaran and Sushant Sachdeva},
booktitle = random12,
year = {2012},
bibsource = {DBLP, http://dblp.uni-trier.de},
pages = {362-373},
doi = {10.1007/978-3-642-32512-0\_31},
note = {Available at \href{http://eccc.hpi-web.de/report/2012/094/}{ECCC}. Preprint at \href{http://arxiv.org/abs/1207.4783}{arXiv}},
}

@article{klz,
title = {Resilient quantum computation},
author = {Emanuel Knill and Raymond Laflamme and Wojciech H. Zurek},
note = {Preprint at \href{http://arxiv.org/abs/quant-ph/9702058}{arXiv}},
journal = {Science},
volume = {279},
number = {5349},
year = {1998},
pages = {342-345},
doi = {10.1126/science.279.5349.342},
}

@proceedings{pstoc83,
booktitle = stoc83,
publisher = acm,
year = {1983}
}
@proceedings{pstoc91,
booktitle = stoc91,
publisher = acm,
year = {1991}
}
@proceedings{pstoc92,
booktitle = stoc92,
publisher = acm,
year = {1992}
}
@proceedings{pstoc97,
booktitle = stoc97,
publisher = acm,
year = {1997}
}
@proceedings{pstoc01,
booktitle = stoc01,
publisher = acm,
year = {2001}
}
@proceedings{pstoc06,
booktitle = stoc06,
publisher = acm,
year = {2006}
}
@proceedings{pstoc10,
booktitle = stoc10,
publisher = acm,
year = {2010}
}


@proceedings{pfocs89,
booktitle = focs89,
publisher = ieee,
year = {1989}
}
@proceedings{pfocs96,
booktitle = focs96,
publisher = ieee,
year = {1996}
}
@proceedings{pfocs99,
booktitle = focs99,
publisher = ieee,
year = {1999}
}
@proceedings{pfocs00,
booktitle = focs00,
publisher = ieee,
year = {2000}
}
