ref.bib

---
---

@book{kitaev2002classical,
  title     = {Classical and quantum computation},
  author    = {Kitaev, Alexei Yu and Shen, Alexander and Vyalyi, Mikhail N and Vyalyi, Mikhail N},
  number    = {47},
  year      = {2002},
  isbn = {9780821832295},
  publisher = {American Mathematical Soc.}
}

@book{katz2014introduction,
  title     = {Introduction to modern cryptography},
  author    = {Katz, Jonathan and Lindell, Yehuda},
  year      = {2014},
  isbn      = {1466570261},
  publisher = {CRC press}
}

@book{kardar2007statistical,
  title     = {Statistical physics of particles},
  author    = {Kardar, Mehran},
  year      = {2007},
  isbn      = {9781139464871},
  publisher = {Cambridge University Press}
}

@book{cormen2009introduction,
  title     = {Introduction to algorithms},
  author    = {Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and Stein, Clifford},
  year      = {2009},
  isbn      = {9780262533058},
  publisher = {MIT press}
}

@book{pathria2011statistical,
  title     = {Statistical mechanics},
  author    = {Pathria, Raj Kumar and Beale, Paul D},
  year      = {2011},
  isbn      = {9780123821898},
  publisher = {Elsevier}
}

@book{g2004principles,
  title     = {Principles of quantum computation and information. Vol. 1: Basic concepts},
  author    = {Benenti, G. and Casati, Giulio and Strini, Giuliano},
  isbn      = {9789812388308},
  year      = {2004},
  publisher = {World Scientific}
}

@book{arora2009computational,
  title     = {Computational complexity: a modern approach},
  author    = {Arora, Sanjeev and Barak, Boaz},
  year      = {2009},
  isbn      = {9780521424264},
  url       = {http://theory.cs.princeton.edu/complexity/},
  publisher = {Cambridge University Press}
}

@book{Nielsen:2011:QCQ:1972505,
  author    = {Nielsen, Michael A. and Chuang, Isaac L.},
  title     = {Quantum Computation and Quantum Information: 10th Anniversary Edition},
  year      = {2011},
  isbn      = {1107002176},
  edition   = {10th},
  publisher = {Cambridge University Press},
  address   = {New York, NY, USA}
} 

@book{altland2010condensed,
  title     = {Condensed matter field theory},
  author    = {Altland, Alexander and Simons, Ben D},
  year      = {2010},
  isbn      = {0521769752},
  publisher = {Cambridge university press}
}

@book{mezard2009information,
  title     = {Information, physics, and computation},
  author    = {Mezard, Marc and Montanari, Andrea},
  year      = {2009},
  isbn      = {9780198570837},
  publisher = {Oxford University Press}
}

@book{nathanson2008elementary,
  title     = {Elementary methods in number theory},
  author    = {Nathanson, Melvyn B},
  volume    = {195},
  year      = {2008},
  isbn      = {9780387227382},
  publisher = {Springer Science \& Business Media}
}

@book{kleinberg2006algorithm,
  title     = {Algorithm design},
  author    = {Kleinberg, Jon and Tardos, Eva},
  year      = {2006},
  isbn      = {9780321295354},
  publisher = {Pearson Education India}
}

@book{zee2010quantum,
  title     = {Quantum field theory in a nutshell},
  author    = {Zee, Anthony},
  volume    = {7},
  year      = {2010},
  isbn      = {9780691140346},
  publisher = {Princeton university press}
}

@book{Kushilevitz:1996:CC:264772,
  author    = {Kushilevitz, Eyal and Nisan, Noam},
  title     = {Communication Complexity},
  year      = {1997},
  isbn      = {0-521-56067-5},
  publisher = {Cambridge University Press},
  address   = {New York, NY, USA}
} 

@book{kremer1995quantum,
  title     = {Quantum communication},
  author    = {Kremer, Ilan},
  year      = {1995},
  publisher = {Citeseer}
}

@book{dasgupta2006algorithms,
  title     = {Algorithms},
  author    = {Dasgupta, Sanjoy and Papadimitriou, Christos H and Vazirani, Umesh},
  year      = {2006},
  publisher = {McGraw-Hill, Inc.}
}

@article{aaronson2020lecture,
  title   = {Quantum Computing Lecture Notes 2.0},
  url     = {https://www.scottaaronson.com/blog/?p=4805},
  author  = {Scott Aaronson},
  journal = {Lecture notes at University of Texas at Austin},
  year    = {2020}
}

@article{childs2017lecture,
  title   = {Lecture notes on quantum algorithms},
  url     = {http://www.cs.umd.edu/~amchilds/qa},
  author  = {Childs, Andrew M},
  journal = {Lecture notes at University of Maryland},
  year    = {2017}
}

@article{Childs_2003,
  title     = {Exponential algorithmic speedup by a quantum walk},
  isbn      = {1581136749},
  doi       = {10.1145/780542.780552},
  journal   = {Proceedings of the thirty-fifth ACM symposium on Theory of computing  - STOC  ’03},
  publisher = {ACM Press},
  author    = {Childs, Andrew M. and Cleve, Richard and Deotto, Enrico and Farhi, Edward and Gutmann, Sam and Spielman, Daniel A.},
  year      = {2003}
}

@article{Childs_2009,
  title     = {On the Relationship Between Continuous- and Discrete-Time Quantum Walk},
  volume    = {294},
  issn      = {1432-0916},
  url       = {http://dx.doi.org/10.1007/s00220-009-0930-1},
  doi       = {10.1007/s00220-009-0930-1},
  number    = {2},
  journal   = {Communications in Mathematical Physics},
  publisher = {Springer Science and Business Media LLC},
  author    = {Childs, Andrew M.},
  year      = {2009},
  month     = {Oct},
  pages     = {581–603}
}


@article{jordan2012quantum,
  title         = {Quantum algorithms for quantum field theories},
  author        = {Jordan, Stephen P and Lee, Keith SM and Preskill, John},
  journal       = {Science},
  volume        = {336},
  number        = {6085},
  pages         = {1130--1133},
  year          = {2012},
  publisher     = {American Association for the Advancement of Science},
  doi           = {10.1126/science.1217069},
  eprint        = {1111.3633},
  archiveprefix = {arXiv},
  primaryclass  = {quant-ph}
}


@article{preskill1998lecture,
  title   = {Lecture notes for physics 229: Quantum information and computation},
  author  = {Preskill, John},
  journal = {California Institute of Technology},
  volume  = {16},
  url     = {http://theory.caltech.edu/~preskill/ph229/},
  year    = {1998}
}


@misc{harrow2020small,
  title         = {Small quantum computers and large classical data sets},
  author        = {Aram W. Harrow},
  year          = {2020},
  eprint        = {2004.00026},
  archiveprefix = {arXiv},
  primaryclass  = {quant-ph}
}

@article{Nayak_2008,
  title     = {\href{http://dx.doi.org/10.1103/RevModPhys.80.1083}{Non-Abelian anyons and topological quantum computation}},
  volume    = {80},
  issn      = {1539-0756},
  number    = {3},
  journal   = {Reviews of Modern Physics},
  publisher = {American Physical Society (APS)},
  author    = {Nayak, Chetan and Simon, Steven H. and Stern, Ady and Freedman, Michael and Das Sarma, Sankar},
  year      = {2008},
  month     = {Sep},
  pages     = {1083–1159}
}

@article{ambainis2017separations,
  title     = {\href{https://arxiv.org/abs/1506.04719}{Separations in query complexity based on pointer functions}},
  author    = {Ambainis, Andris and Balodis, Kaspars and Belovs, Aleksandrs and Lee, Troy and Santha, Miklos and Smotrovs, Juris},
  journal   = {Journal of the ACM (JACM)},
  volume    = {64},
  number    = {5},
  pages     = {32},
  year      = {2017},
  publisher = {ACM}
}

@article{kalyanasundaram1992probabilistic,
  title     = {\href{https://epubs.siam.org/doi/abs/10.1137/0405044}{The probabilistic communication complexity of set intersection}},
  author    = {Kalyanasundaram, Bala and Schintger, Georg},
  journal   = {SIAM Journal on Discrete Mathematics},
  volume    = {5},
  number    = {4},
  pages     = {545--557},
  year      = {1992},
  publisher = {SIAM}
}

@inproceedings{buhrman1998quantum,
  title        = {\href{https://arxiv.org/abs/quant-ph/9802040}{Quantum vs. classical communication and computation}},
  author       = {Buhrman, Harry and Cleve, Richard and Wigderson, Avi},
  booktitle    = {Proceedings of the thirtieth annual ACM symposium on Theory of computing},
  pages        = {63--68},
  year         = {1998},
  organization = {ACM}
}

@inproceedings{raz1999exponential,
  title        = {\href{https://dl.acm.org/citation.cfm?id=301343}{Exponential separation of quantum and classical communication complexity}},
  author       = {Raz, Ran},
  booktitle    = {Proceedings of the thirty-first annual ACM symposium on Theory of computing},
  pages        = {358--367},
  year         = {1999},
  organization = {ACM}
}

@article{shor1999polynomial,
  title     = {\href{https://arxiv.org/abs/quant-ph/9508027}{Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer}},
  author    = {Shor, Peter W},
  journal   = {SIAM review},
  volume    = {41},
  number    = {2},
  pages     = {303--332},
  year      = {1999},
  publisher = {SIAM}
}

@inproceedings{grover1996fast,
  title        = {\href{https://arxiv.org/abs/quant-ph/9605043}{A fast quantum mechanical algorithm for database search}},
  author       = {Grover, Lov K},
  booktitle    = {Proceedings of the twenty-eighth annual ACM symposium on Theory of computing},
  pages        = {212--219},
  year         = {1996},
  organization = {ACM}
}

@article{deutsch1992rapid,
  title     = {\href{http://rspa.royalsocietypublishing.org/content/439/1907/553}{Rapid solution of problems by quantum computation}},
  author    = {Deutsch, David and Jozsa, Richard},
  journal   = {Proc. R. Soc. Lond. A},
  volume    = {439},
  number    = {1907},
  pages     = {553--558},
  year      = {1992},
  publisher = {The Royal Society}
}

@inproceedings{brassard1997exact,
  title        = {\href{https://arxiv.org/abs/quant-ph/9704027}{An exact quantum polynomial-time algorithm for Simon's problem}},
  author       = {Brassard, Gilles and Hoyer, Peter},
  booktitle    = {Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on},
  pages        = {12--23},
  year         = {1997},
  organization = {IEEE}
}

@article{simon1997power,
  title     = {\href{https://epubs.siam.org/doi/10.1137/S0097539796298637}{On the power of quantum computation}},
  author    = {Simon, Daniel R},
  journal   = {SIAM journal on computing},
  volume    = {26},
  number    = {5},
  pages     = {1474--1483},
  year      = {1997},
  publisher = {SIAM}
}

@article{brassard1997quantum,
  title         = {Quantum cryptanalysis of hash and claw-free functions},
  isbn          = {9783540697152},
  issn          = {1611-3349},
  url           = {http://dx.doi.org/10.1007/BFb0054319},
  doi           = {10.1007/bfb0054319},
  eprint        = {quant-ph/9705002},
  archiveprefix = {arXiv},
  journal       = {Lecture Notes in Computer Science},
  publisher     = {Springer Berlin Heidelberg},
  author        = {Brassard, Gilles and HØyer, Peter and Tapp, Alain},
  year          = {1998},
  pages         = {163–169}
}

@article{razborov2003quantum,
  title     = {\href{https://arxiv.org/abs/quant-ph/0204025}{Quantum communication complexity of symmetric predicates}},
  author    = {Razborov, Alexander A},
  journal   = {Izvestiya: Mathematics},
  volume    = {67},
  number    = {1},
  pages     = {145},
  year      = {2003},
  publisher = {IOP Publishing}
}

@article{boyer1998tight,
  title     = {\href{https://arxiv.org/abs/quant-ph/9605034}{Tight bounds on quantum searching}},
  author    = {Boyer, Michel and Brassard, Gilles and H{\o}yer, Peter and Tapp, Alain},
  journal   = {Fortschritte der Physik: Progress of Physics},
  volume    = {46},
  number    = {4-5},
  pages     = {493--505},
  year      = {1998},
  publisher = {Wiley Online Library}
}
        
@inproceedings{aaronson2003quantum,
  title        = {\href{https://arxiv.org/abs/quant-ph/0303041}{Quantum search of spatial regions}},
  author       = {Aaronson, Scott and Ambainis, Andris},
  booktitle    = {Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on},
  pages        = {200--209},
  year         = {2003},
  organization = {IEEE}
}

@article{buhrman2001quantum,
  title     = {\href{https://arxiv.org/abs/quant-ph/0102001}{Quantum fingerprinting}},
  author    = {Buhrman, Harry and Cleve, Richard and Watrous, John and De Wolf, Ronald},
  journal   = {Physical Review Letters},
  volume    = {87},
  number    = {16},
  pages     = {167902},
  year      = {2001},
  publisher = {APS}
}

@inproceedings{aaronson2016separations,
  title        = {\href{https://arxiv.org/abs/1511.01937}{Separations in query complexity using cheat sheets}},
  author       = {Aaronson, Scott and Ben-David, Shalev and Kothari, Robin},
  booktitle    = {Proceedings of the forty-eighth annual ACM symposium on Theory of Computing},
  pages        = {863--876},
  year         = {2016},
  organization = {ACM}
}

@article{sherstov2013approximating,
  title   = {\href{http://www.theoryofcomputing.org/articles/v009a020/}{Approximating the AND-OR Tree.}},
  author  = {Sherstov, Alexander A},
  journal = {Theory of Computing},
  volume  = {9},
  number  = {20},
  pages   = {653--663},
  year    = {2013}
}

@inproceedings{hoyer2003quantum,
  title        = {\href{https://arxiv.org/abs/quant-ph/0304052}{Quantum search on bounded-error inputs}},
  author       = {H{\o}yer, Peter and Mosca, Michele and De Wolf, Ronald},
  booktitle    = {International Colloquium on Automata, Languages, and Programming},
  pages        = {291--299},
  year         = {2003},
  organization = {Springer}
}

@article{nisan1994degree,
  title     = {\href{https://dl.acm.org/citation.cfm?id=129757}{On the degree of Boolean functions as real polynomials}},
  author    = {Nisan, Noam and Szegedy, Mario},
  journal   = {Computational complexity},
  volume    = {4},
  number    = {4},
  pages     = {301--313},
  year      = {1994},
  publisher = {Springer}
}

@article{rubinstein1995sensitivity,
  title     = {\href{https://link.springer.com/article/10.1007/BF01200762}{Sensitivity vs. block sensitivity of Boolean functions}},
  author    = {Rubinstein, David},
  journal   = {Combinatorica},
  volume    = {15},
  number    = {2},
  pages     = {297--299},
  year      = {1995},
  publisher = {Springer}
}

@article{brassard2002quantum,
  title     = {\href{https://arxiv.org/abs/quant-ph/0005055}{Quantum amplitude amplification and estimation}},
  author    = {Brassard, Gilles and Hoyer, Peter and Mosca, Michele and Tapp, Alain},
  journal   = {Contemporary Mathematics},
  volume    = {305},
  pages     = {53--74},
  year      = {2002},
  publisher = {Providence, RI; American Mathematical Society; 1999}
}

@inproceedings{yao1979some,
  title        = {\href{https://dl.acm.org/citation.cfm?id=804414}{Some complexity questions related to distributive computing (preliminary report)}},
  author       = {Yao, Andrew Chi-Chih},
  booktitle    = {Proceedings of the eleventh annual ACM symposium on Theory of computing},
  pages        = {209--213},
  year         = {1979},
  organization = {ACM}
}

@article{beals2001quantum,
  title     = {\href{https://arxiv.org/abs/quant-ph/9802049}{Quantum lower bounds by polynomials}},
  author    = {Beals, Robert and Buhrman, Harry and Cleve, Richard and Mosca, Michele and De Wolf, Ronald},
  journal   = {Journal of the ACM (JACM)},
  volume    = {48},
  number    = {4},
  pages     = {778--797},
  year      = {2001},
  publisher = {ACM}
}

@inproceedings{razborov1990distributional,
  title        = {On the distributional complexity of disjointness},
  author       = {Razborov, Alexander A},
  booktitle    = {International Colloquium on Automata, Languages, and Programming},
  url          = {https://link.springer.com/chapter/10.1007%2FBFb0032036},
  pages        = {249--253},
  year         = {1990},
  organization = {Springer}
}

@inproceedings{mehlhorn1982vegas,
  title        = {\href{https://dl.acm.org/citation.cfm?id=802208}{Las Vegas is better than determinism in VLSI and distributed computing}},
  author       = {Mehlhorn, Kurt and Schmidt, Erik M},
  booktitle    = {Proceedings of the fourteenth annual ACM symposium on Theory of computing},
  pages        = {330--337},
  year         = {1982},
  organization = {ACM}
}

@article{buhrman2005quantum,
  title     = {\href{https://arxiv.org/abs/quant-ph/0007016}{Quantum algorithms for element distinctness}},
  author    = {Buhrman, Harry and D{\"u}rr, Christoph and Heiligman, Mark and H{\o}yer, Peter and Magniez, Fr{\'e}d{\'e}ric and Santha, Miklos and de Wolf, Ronald},
  journal   = {SIAM Journal on Computing},
  volume    = {34},
  number    = {6},
  pages     = {1324--1330},
  year      = {2005},
  publisher = {SIAM}
}

@article{ambainis2010any,
  title     = {\href{https://epubs.siam.org/doi/abs/10.1137/080712167}{Any AND-OR formula of size N can be evaluated in time N\^{}1/2+o(1) on a quantum computer}},
  author    = {Ambainis, Andris and Childs, Andrew M and Reichardt, Ben W and {\v{S}}palek, Robert and Zhang, Shengyu},
  journal   = {SIAM Journal on Computing},
  volume    = {39},
  number    = {6},
  pages     = {2513--2530},
  year      = {2010},
  publisher = {SIAM}
}

@article{ambainis2007quantum,
  title     = {\href{https://arxiv.org/abs/quant-ph/0311001}{Quantum walk algorithm for element distinctness}},
  author    = {Ambainis, Andris},
  journal   = {SIAM Journal on Computing},
  volume    = {37},
  number    = {1},
  pages     = {210--239},
  year      = {2007},
  publisher = {SIAM}
}

@article{aaronson2004quantum,
  title     = {\href{https://arxiv.org/abs/quant-ph/0112086}{Quantum lower bounds for the collision and the element distinctness problems}},
  author    = {Aaronson, Scott and Shi, Yaoyun},
  journal   = {Journal of the ACM (JACM)},
  volume    = {51},
  number    = {4},
  pages     = {595--605},
  year      = {2004},
  publisher = {ACM}
}

@inproceedings{brassard1998quantum,
  title        = {\href{https://arxiv.org/abs/quant-ph/9805082}{Quantum counting}},
  author       = {Brassard, Gilles and H{\o}yer, Peter and Tapp, Alain},
  booktitle    = {International Colloquium on Automata, Languages, and Programming},
  pages        = {820--831},
  year         = {1998},
  organization = {Springer}
}


@article{agrawal2004primes,
  title     = {\href{http://www.jstor.org/stable/3597229}{PRIMES is in P}},
  author    = {Agrawal, Manindra and Kayal, Neeraj and Saxena, Nitin},
  journal   = {Annals of mathematics},
  pages     = {781--793},
  year      = {2004},
  publisher = {JSTOR}
}

@article{deutsch1985quantum,
  title     = {\href{http://rspa.royalsocietypublishing.org/content/400/1818/97.short}{Quantum theory, the Church--Turing principle and the universal quantum computer}},
  author    = {Deutsch, David},
  journal   = {Proc. R. Soc. Lond. A},
  volume    = {400},
  number    = {1818},
  pages     = {97--117},
  year      = {1985},
  publisher = {The Royal Society}
}


@article{frankl1987forbidden,
  title   = {\href{http://www.ams.org/journals/tran/1987-300-01/S0002-9947-1987-0871675-6/}{Forbidden intersections}},
  author  = {Frankl, Peter and R{\"o}dl, Vojt{\v{e}}ch},
  journal = {Transactions of the American Mathematical Society},
  volume  = {300},
  number  = {1},
  pages   = {259--286},
  year    = {1987}
}

@article{de2002quantum,
  title     = {\href{https://www.sciencedirect.com/science/article/pii/S0304397502003778}{Quantum communication and complexity}},
  author    = {De Wolf, Ronald},
  journal   = {Theoretical computer science},
  volume    = {287},
  number    = {1},
  pages     = {337--353},
  year      = {2002},
  publisher = {Elsevier}
}

@inproceedings{de2000characterization,
  title        = {\href{https://ieeexplore.ieee.org/abstract/document/856758/}{Characterization of non-deterministic quantum query and quantum communication complexity}},
  author       = {De Wolf, Ronald},
  booktitle    = {Computational Complexity, 2000. Proceedings. 15th Annual IEEE Conference on},
  pages        = {271--278},
  year         = {2000},
  organization = {IEEE}
}

@inproceedings{buhrman1999bounds,
  title        = {\href{https://arxiv.org/abs/cs/9904019}{Bounds for small-error and zero-error quantum algorithms}},
  author       = {Buhrman, Harry and Cleve, Richard and De Wolf, Ronald and Zalka, Christof},
  booktitle    = {Foundations of Computer Science, 1999. 40th Annual Symposium on},
  pages        = {358--368},
  year         = {1999},
  organization = {IEEE}
}

@inproceedings{klauck2000quantum,
  title        = {\href{https://dl.acm.org/citation.cfm?id=335396}{On quantum and probabilistic communication: Las Vegas and one-way protocols}},
  author       = {Klauck, Hartmut},
  booktitle    = {Proceedings of the thirty-second annual ACM symposium on Theory of computing},
  pages        = {644--651},
  year         = {2000},
  organization = {ACM}
}

@article{shi2007quantum,
  title         = {Quantum communication complexity of block-composed functions},
  author        = {Yaoyun Shi and Yufan Zhu},
  eprint        = {0710.0095},
  archiveprefix = {arXiv},
  primaryclass  = {quant-ph},
  year          = {2008},
  journal       = {Quantum Inf. Comput.},
  volume        = {9},
  pages         = {444-460}
}

@inproceedings{montanaro2008unbounded,
  title        = {\href{https://arxiv.org/abs/0712.1446}{Unbounded-error quantum query complexity}},
  author       = {Montanaro, Ashley and Nishimura, Harumichi and Raymond, Rudy},
  booktitle    = {International Symposium on Algorithms and Computation},
  pages        = {919--930},
  year         = {2008},
  organization = {Springer}
}

@inproceedings{ambainis2003polynomial,
  title        = {\href{https://arxiv.org/abs/quant-ph/0305028}{Polynomial degree vs. quantum query complexity}},
  author       = {Ambainis, Andris},
  booktitle    = {Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on},
  pages        = {230--239},
  year         = {2003},
  organization = {IEEE}
}

@article{montanaro2015exact,
  title     = {\href{https://arxiv.org/abs/1111.0475}{On exact quantum query complexity}},
  author    = {Montanaro, Ashley and Jozsa, Richard and Mitchison, Graeme},
  journal   = {Algorithmica},
  volume    = {71},
  number    = {4},
  pages     = {775--796},
  year      = {2015},
  publisher = {Springer}
}


@inproceedings{saks1986probabilistic,
  title        = {\href{https://ieeexplore.ieee.org/abstract/document/4568192/}{Probabilistic Boolean decision trees and the complexity of evaluating game trees}},
  author       = {Saks, Michael and Wigderson, Avi},
  booktitle    = {Foundations of Computer Science, 1986., 27th Annual Symposium on},
  pages        = {29--38},
  year         = {1986},
  organization = {IEEE}
}

@inproceedings{aaronson2015forrelation,
  title        = {\href{https://arxiv.org/abs/1411.5729}{Forrelation: A problem that optimally separates quantum from classical computing}},
  author       = {Aaronson, Scott and Ambainis, Andris},
  booktitle    = {Proceedings of the forty-seventh annual ACM symposium on Theory of computing},
  pages        = {307--316},
  year         = {2015},
  organization = {ACM}
}

@article{long2001grover,
  title     = {\href{https://arxiv.org/abs/quant-ph/0106071}{Grover algorithm with zero theoretical failure rate}},
  author    = {Long, Gui-Lu},
  journal   = {Physical Review A},
  volume    = {64},
  number    = {2},
  pages     = {022307},
  year      = {2001},
  publisher = {APS}
}

@inproceedings{goos2015deterministic,
  title        = {\href{https://ieeexplore.ieee.org/abstract/document/7354444/}{Deterministic communication vs. partition number}},
  author       = {G{\"o}{\"o}s, Mika and Pitassi, Toniann and Watson, Thomas},
  booktitle    = {Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on},
  pages        = {1077--1088},
  year         = {2015},
  organization = {IEEE}
}

@article{buhrman2002complexity,
  title     = {Complexity measures and decision tree complexity: a survey},
  author    = {Buhrman, Harry and De Wolf, Ronald},
  journal   = {Theoretical Computer Science},
  volume    = {288},
  number    = {1},
  pages     = {21--43},
  year      = {2002},
  url       = {https://www.sciencedirect.com/science/article/pii/S030439750100144X?via%3Dihub},
  publisher = {Elsevier}
}

@article{ambainis2002quantum,
  title     = {\href{https://arxiv.org/abs/quant-ph/0002066}{Quantum lower bounds by quantum arguments}},
  author    = {Ambainis, Andris},
  journal   = {Journal of Computer and System Sciences},
  volume    = {64},
  number    = {4},
  pages     = {750--767},
  year      = {2002},
  publisher = {Elsevier}
}

@article{alon1999space,
  title     = {\href{https://m.tau.ac.il/~nogaa/PDFS/amsz4.pdf}{The space complexity of approximating the frequency moments}},
  author    = {Alon, Noga and Matias, Yossi and Szegedy, Mario},
  journal   = {Journal of Computer and system sciences},
  volume    = {58},
  number    = {1},
  pages     = {137--147},
  year      = {1999},
  publisher = {Elsevier}
}


@article{troyer2005computational,
  title     = {Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations},
  author    = {Troyer, Matthias and Wiese, Uwe-Jens},
  journal   = {Physical review letters},
  volume    = {94},
  number    = {17},
  pages     = {170201},
  year      = {2005},
  publisher = {APS}
}

@article{strubell2011introduction,
  title   = {An introduction to quantum algorithms},
  author  = {Strubell, Emma},
  journal = {COS498 Chawathe Spring},
  volume  = {13},
  pages   = {19},
  year    = {2011}
}

@article{hardy1918asymptotic,
  title     = {Asymptotic formula{\ae} in combinatory analysis},
  author    = {Hardy, Godfrey H and Ramanujan, Srinivasa},
  journal   = {Proceedings of the London Mathematical Society},
  volume    = {2},
  number    = {1},
  pages     = {75--115},
  year      = {1918},
  url       = {http://ramanujan.sirinudi.org/Volumes/published/ram36.pdf},
  publisher = {Wiley Online Library}
}

@article{weiss1997particle,
  title     = {Particle number counting statistics in ideal Bose gases},
  author    = {Weiss, Christoph and Wilkens, Martin},
  journal   = {Optics Express},
  volume    = {1},
  number    = {10},
  pages     = {272--283},
  year      = {1997},
  publisher = {Optical Society of America}
}


@article{strassen1969gaussian,
  title     = {Gaussian elimination is not optimal},
  author    = {Strassen, Volker},
  journal   = {Numerische mathematik},
  volume    = {13},
  number    = {4},
  pages     = {354--356},
  year      = {1969},
  publisher = {Springer}
}


@article{arad2008quantum,
  author        = {Arad, Itai and Landau, Zeph},
  title         = {Quantum Computation and the Evaluation of Tensor Networks},
  journal       = {SIAM J. Comput.},
  issue_date    = {May 2010},
  volume        = {39},
  number        = {7},
  month         = jun,
  year          = {2010},
  issn          = {0097-5397},
  pages         = {3089--3121},
  numpages      = {33},
  doi           = {10.1137/080739379},
  acmid         = {1958071},
  publisher     = {Society for Industrial and Applied Mathematics},
  address       = {Philadelphia, PA, USA},
  keywords      = {quantum algorithms, statistical mechanical models, tensor networks},
  eprint        = {0805.0040},
  archiveprefix = {arXiv},
  primaryclass  = {quant-ph}
}

@misc{0805.0040,
  author = {Itai Arad and Zeph Landau},
  title  = {{Q}uantum computation and the evaluation of tensor networks},
  year   = {2008},
  eprint = {0805.0040},
  note   = {arXiv:0805.0040v3}
}


@misc{farhi2014quantum,
  title         = {A Quantum Approximate Optimization Algorithm},
  author        = {Edward Farhi and Jeffrey Goldstone and Sam Gutmann},
  year          = {2014},
  eprint        = {1411.4028},
  archiveprefix = {arXiv},
  primaryclass  = {quant-ph}
}

@article{cleve1998quantum,
  title         = {Quantum algorithms revisited},
  author        = {Cleve, Richard and Ekert, Artur and Macchiavello, Chiara and Mosca, Michele},
  journal       = {Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences},
  volume        = {454},
  number        = {1969},
  pages         = {339--354},
  year          = {1998},
  doi           = {10.1098/rspa.1998.0164},
  eprint        = {quant-ph/9708016},
  archiveprefix = {arXiv},
  primaryclass  = {quant-ph},
  url           = {https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.1998.0164},
  publisher     = {The Royal Society}
}

@article{nayak2000quantum,
    title   = {Quantum walk on the line},
    author  = {Nayak, Ashwin and Vishwanath, Ashvin},
    journal = {arXiv preprint quant-ph/0010117},
    archivePrefix = {arXiv},
    eprint = {quant-ph/0010117},
    primaryClass = {quant-ph},
    year    = {2000}
}

@inproceedings{ambainis2001one,
  title     = {One-dimensional quantum walks},
  author    = {Ambainis, Andris and Bach, Eric and Nayak, Ashwin and Vishwanath, Ashvin and Watrous, John},
  booktitle = {Proceedings of the thirty-third annual ACM symposium on Theory of computing},
  pages     = {37--49},
  url = {https://doi.org/10.1145/380752.380757},
    doi = {10.1145/380752.380757},
  year      = {2001}
}

@article{farhi1998quantum,
  title     = {Quantum computation and decision trees},
  author    = {Farhi, Edward and Gutmann, Sam},
  journal   = {Physical Review A},
  volume    = {58},
  number    = {2},
  pages     = {915},
  year      = {1998},
    doi = {10.1103/PhysRevA.58.915},
    archivePrefix = {arXiv},
    eprint = {quant-ph/9706062},
  publisher = {APS}
}

@article{childs2002example,
  title     = {An example of the difference between quantum and classical random walks},
  author    = {Childs, Andrew M and Farhi, Edward and Gutmann, Sam},
  journal   = {Quantum Information Processing},
  volume    = {1},
  number    = {1-2},
  pages     = {35--43},
  year      = {2002},
  url             = {https://link.springer.com/article/10.1023/A:1019609420309},
  archivePrefix = {arXiv},
       eprint = {quant-ph/0103020},
  publisher = {Springer}
}


@article{shenvi2003quantum,
  title     = {Quantum random-walk search algorithm},
  author    = {Shenvi, Neil and Kempe, Julia and Whaley, K Birgitta},
  journal   = {Physical Review A},
  volume    = {67},
  number    = {5},
  pages     = {052307},
  year      = {2003},
    doi = {10.1103/PhysRevA.67.052307},
    archivePrefix = {arXiv},
    eprint = {quant-ph/0210064},
  publisher = {APS}
}

@article{childsUniversalComputationQuantum2009,
  title         = {Universal Computation by Quantum Walk},
  author        = {Childs, Andrew M.},
  date          = {2009-05-04},
  journaltitle  = {Physical Review Letters},
  shortjournal  = {Phys. Rev. Lett.},
  volume        = {102},
  pages         = {180501},
  issn          = {0031-9007, 1079-7114},
  doi           = {10.1103/PhysRevLett.102.180501},
  url           = {http://arxiv.org/abs/0806.1972},
  urldate       = {2020-11-30},
  abstract      = {In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes.},
  archiveprefix = {arXiv},
  eprint        = {0806.1972},
  eprinttype    = {arxiv},
  file          = {/Users/jue/Zotero/storage/JS8ZWQYP/Childs - 2009 - Universal computation by quantum walk.pdf},
  keywords      = {Quantum Physics},
  langid        = {english},
  number        = {18}
}


@article{qutip1,
  doi       = {10.1016/j.cpc.2012.02.021},
  url       = {https://doi.org/10.1016/j.cpc.2012.02.021},
  year      = {2012},
  month     = {aug},
  publisher = {Elsevier {BV}},
  volume    = {183},
  number    = {8},
  pages     = {1760--1772},
  author    = {J.R. Johansson and P.D. Nation and F. Nori},
  title     = {{QuTiP}: An open-source {P}ython framework for the dynamics of open quantum systems},
  journal   = {Computer Physics Communications}
}