@Article{Qutrits, author = {Janzing, D.}, title = {Spin-1/2 particles moving on a 2D lattice with nearest-neighbor interactions can realize an autonomous quantum computer}, journal = {Physical Review}, year = {2007}, volume = {A}, number = {75}, pages = {012307}, eprint = {pra:10.1103/PhysRevA.75.012307}, } @Unpublished{aharonov-2003, author = {Aharonov, D.}, title = {A simple proof that {Toffoli} and {Hadamard} are quantum universal}, year = {2003}, eprint = {arxiv:quant-ph/0301040}, } @Article{esy:promise, author ={Even, S. and Selman, {A.~L.} and Yacobi, Y.}, title = {The complexity of promise problems with applications to public-key cryptography}, journal = {Inform. and Control}, vol ={61}, pages = {159--173}, year = {1984} } @Article{BernVaz, author = {Bernstein, E. and Vazirani, U.}, title = {Quantum Complexity Theory}, journal = {SIAM Journal on Computing}, year = {1997}, volume = {26}, number = {5}, pages = {1411--1473}, eprint="sicomp:10.1137/S0097539796300921" } @Article{KnillQuadr, author = {Knill, E. and Laflamme, R.}, title = {Quantum computation and quadratically signed weight enumerators}, year ={2001}, journal = {Inf. Process. Lett.}, volume = {79}, number = {4}, page = {173--179}, eprint="ipl:10.1016/S0020-0190(00)00222-2" } @Unpublished{PawelYard, author = {Wocjan, P. and Yard, J.}, title = {The {Jones} polynomial: quantum algorithms and applications in quantum complexity theory}, year = {2006}, eprint= {arxiv:quant-ph/0603069}, pdf ="http://arxiv.org/abs/quant-ph/0603069.pdf" } @Unpublished{aharonov-2006-, author = "Aharonov, D. and Arad, I.", title = {The {BQP}-hardness of approximating the {Jones} polynomial}, year = {2006}, eprint = {arxiv:quant-ph/0605181}, pdf = "http://arxiv.org/abs/quant-ph/0605181.pdf" } @Unpublished{WZ:06, author = "Wocjan, P. and Zhang, S.", title = {Several natural {BQP}-complete problems}, year = {2006}, eprint = {arxiv:quant-ph/0606179}, } @Article{Ergodic, author = {Janzing, D. and Wocjan, P.}, title = "Ergodic quantum computing", year ={2005}, journal = "Quant. Inf. Process.", volume = {4}, number = {2}, pages = {129--158}, eprint = {springer:wq1g61v1236574t4} } @Book{KitaevShen, author = "Kitaev, A. and Shen, A. and Vyalyi, M.", title = "Classical and Quantum Computation", year = {2002}, publisher = {Am. Math. Soc.}, address = {Providence, Rhode Island} } @Unpublished{Oliveira, author = "Oliveira, R. and Terhal, B.", title = "The complexity of quantum spin systems on a two-dimensional square lattice", eprint= {arxiv:quant-ph/0504050}, year = {2005}, pdf = "http://arxiv.org/abs/quant-ph/0504050" } @article{Kempe2local, author = {Kempe, J. and Kitaev, A. and Regev, O.}, title = {The complexity of the local {Hamiltonian} problem}, year = 2006, pages = {1070--1097}, journal="SIAM J. Computing", volume=35, number=5, eprint="sicomp:10.1137/S0097539704445226" } @Article{RB00, title = {A One-Way Quantum Computer}, author = {Raussendorf, R. and Briegel, H.}, journal = {Phys. Rev. Lett.}, volume = {86}, number = {22}, pages = {5188--5191}, numpages = {3}, year = {2001}, eprint = {prl:10.1103/PhysRevLett.86.5188}, } @Article{RB00b, author = {Raussendorf, R. and Briegel, H.}, title = {Quantum computing via measurement only}, year ={2000}, journal = {Phys. Rev. Lett}, pages = {5188} } @Unpublished{browne-2006-, author = {Browne, {D. E.} and Briegel, H.}, title = {One-way quantum computation - a tutorial introduction}, year = {2006}, eprint = {arxiv:quant-ph/0603226} } @Article{childs-2005-71, author = {{A.~M.} Childs and {D.~W.} Leung and {M.~A.} Nielsen}, title = {Unified derivations of measurement-based schemes for quantum computation}, journal = {Phys. Rev. A}, volume = {71}, pages = {032318}, year ={2005}, eprint = {pra:10.1103/PhysRevA.71.032318} } @InProceedings{ATS, author = {Aharonov, D. and Ta-Shma, A.}, title = {Adiabatic quantum state generation and statistical zero knowledge}, booktitle = {Proc. 35th Annual ACM Symp. on Theory of Computing}, pages = {20--29}, year = {2003}, eprint="stoc:10.1145/780542.780546" } @PhdThesis{ChildsDiss, author = {Childs, A.}, title = {Quantum information processing in continuous time}, school = {Massachusetts Institute of Technology}, year = {2004}, } @Article{Hoeffding, author = {Hoeffding, W.}, title = {Probability inequalities for sums of bounded random variables}, journal = {Journ. Am. Stat. Ass.}, year = {1963}, volume = {58}, number = {301}, pages = {13--30}, } @Article{BACS:06, author = {Berry, {D. W.} and Ahokas, G. and Cleve, R. and Sanders, {B. C.}}, title = {Efficient quantum algorithms for simulating sparse {Hamiltonians}}, journal = {Comm. Math. Phys.}, year = {2007}, volume = {270}, number = {2}, pages = {359--371}, OPTnote = {\url{http://www.springerlink.com/content/hk7484445j37r228/?p=09b4525efac543d381ab1975f8a1595f&pi=2}}, OPTannote = {}, eprint="springer:hk7484445j37r228" } @Book{NC, author = {M. Nielsen and I. Chuang}, title = {Quantum Computation and Quantum Information}, publisher = {Cambridge University Press}, year = {2000}, } @InProceedings{PSPACE, author = {Wocjan, P. and Janzing, D. and Decker, Th. and Beth, Th.}, title = {Measuring 4-local n-qubit observables could probabilistically solve {PSPACE}}, booktitle = {Proc. Winter International Symp. on Information and Communication Technologies}, year = {2004}, note = {(Proceedings contain only the abstract) }, eprint= {arxiv:quant-ph/0308011}, } @Article{IdentityQMA, author = {Janzing, D. and Wocjan, P. and Beth, T.}, title = {``{N}on-{I}dentity check'' is {QMA}-complete}, journal = {Int. Journ. Quant. Inf.}, year = {2005}, OPTkey = {}, volume = {3}, number=3, pages = {463--473}, OPTmonth = {}, doi = {10.1142/S0219749905001067}, url = {http://www.worldscinet.com/ijqi/03/0303/S0219749905001067.html}, OPTannote = {} } @Article{Freedman, author = {Freedman, M. and Kitaev, A. and Wang, Z.}, title = {Simulation of topological field theories by quantum computers}, journal = {Comm. Math. Phys.}, volume = {227}, number = {3}, year = {2002}, pages = {587--603}, eprint="springer:btldwt3g5t0308da" } @Unpublished{Landau, author = {Aharonov, D. and Jones, V. and Landau, Z.}, title = {A Polynomial Quantum Algorithm for Approximating the {Jones} Polynomial}, year = {2005}, eprint= {arxiv:quant-ph/0511096} } @TechReport{goldreich:promise, author = {Goldreich, O.}, title = {On promise problems}, institution = {Electr. Colloquium Computational Complexity}, year = {2005}, OPTkey = {}, OPTvolume = {}, number = {18}, OPTpages = {}, OPTmonth = {}, url = {http://eccc.hpi-web.de/eccc-reports/2005/TR05-018/index.html}, OPTannote = {}, eprint="eccc:TR05-018" }