Publications Wim van Dam

  1. Necessary adiabatic run times in quantum optimization,
    Lucas T. Brady and Wim van Dam,
    Physical Review A, Volume 95, Issue 3, Article 032335 (2017)
    arXiv:1611.02585
  2. Discrepancies between asymptotic and exact spectral gap analyses of quantum adiabatic tunneling,
    Lucas T. Brady and Wim van Dam,
    Physical Review A, Volume 95, Issue 5, Article 052350 (2017)
    arXiv:1609.09137
  3. Spectral-gap analysis for efficient tunneling in quantum adiabatic optimization,
    Lucas T. Brady and Wim van Dam,
    Physical Review A, Volume 94, Issue 3, Article 032309 (2016)
    arXiv:1601.01720
  4. Optimal quantum algorithm for polynomial interpolation,
    Andrew M. Childs, Wim van Dam, Shih-Han Hung, and Igor E. Shparlinski,
    43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 16:1-16:13 (2016)
    doi:10.4230/LIPIcs.ICALP.2016.16
    arXiv:1509.09271
  5. Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization,
    Lucas T. Brady and Wim van Dam,
    Physical Review A, Volume 93, Issue 3, Article 032304 (2016);
    arXiv:1509.02562
  6. Hidden Subgroup Quantum Algorithms for a Class of Semi-Direct Product Groups,
    Wim van Dam and Siladitya Dey,
    9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014), Leibniz International Proceedings in Informatics (LIPIcs), volume 27, editors Steven T. Flammia and Aram W. Harrow, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pages 110-117 (2014)
  7. Minimum Energy Surface Required by Quantum Memory Devices,
    Wim van Dam and Hieu D. Nguyen,
    Physical Review Letters, Volume 110, Issue 25, Article 250502 (2013);
    arXiv:1212.3707
  8. Quantum algorithms for problems in number theory, algebraic geometry, and group theory,
    Wim van Dam and Yoshitaka Sasaki,
    Diversities in Quantum Computation and Quantum Information, Kinki University Series on Quantum Computing, Volume 5, edited by Mikio Nakahara, Yidun Wan, and Yoshitaka Sasaki, pages 79-103 (2012); arXiv:1206.6126
  9. Decoherent histories of quantum searching,
    Wim van Dam and Hieu D. Nguyen,
    arXiv:1206.1946
  10. Mutually unbiased bases for quantum states defined over p-adic numbers,
    Wim van Dam and Alexander Russell,
    arXiv:1109.0060
  11. Bipartite entangled stabilizer mutually unbiased bases as maximum cliques of Cayley graphs,
    Wim van Dam and Mark Howard,
    Physical Review A, Volume 84, Issue 1, Article 012117 (2011);
    arXiv:1104.0945
  12. Noise thresholds for higher dimensional systems using the discrete Wigner function,
    Wim van Dam and Mark Howard,
    Physical Review A, Volume 83, Issue 3, Article 032310 (2011);
    arXiv:1011.2497
  13. Theory of Quantum Computation, Communication and Cryptography (TQC 2010),
    5th Conference, TQC 2010, Leeds, UK, April 13-15, 2010, revised selected papers,
    editors: Wim van Dam, Vivien M. Kendon and Simone Severini,
    Lecture Notes in Computer Science, Volume 6519 (2011)
  14. Recent Progress in Quantum Algorithms,
    Dave Bacon and Wim van Dam,
    Communications of the ACM, Volume 53, Number 2, pages 84-93 (February 2010)
  15. Quantum Online Memory Checking,
    Wim van Dam and Qingqing Yuan,
    Theory of Quantum Computation, Communication, and Cryptography: Fourth Workshop, TQC 2009, Waterloo, Canada, May 11-13, 2009. Revised Selected Papers, eds. Andrew Childs and Michele Mosca, Lecture Notes in Computer Science, Volume 5906, Springer, pages 10-19 (2009);
    arXiv:1002.2970
  16. Tight Noise Thresholds for Quantum Computation with Perfect Stabilizer Operations,
    Wim van Dam and Mark Howard,
    Physical Review Letters, Volume 103, Number 17, Article 170504 (2009);
    arXiv:0907.3189
  17. Analyzing Algebraic Quantum Circuits Using Exponential Sums,
    Dave Bacon, Wim van Dam, Alexander Russell,
    draft (November 2008)
  18. Quantum Algorithms for Algebraic Problems,
    Andrew M. Childs and Wim van Dam,
    Reviews of Modern Physics, Volume 82, Number 1, pages 1-52 (January 2010);
    arXiv:0812.0380
  19. Inside Information (book review of David Mermin's Quantum Information Science),
    Wim van Dam,
    American Scientist, Volume 96, Number 5, pages 431-432, (September-October 2008);
    doi:10.1511/2008.74.431
  20. Classical and Quantum Algorithms for Exponential Congruences,
    Wim van Dam and Igor E. Shparlinski,
    Proceedings of the Third Workshop on Theory of Quantum Computation, Communication and Cryptography (TQC 2008), Lecture Notes in Computer Science, Volume 5106, pages 1-10 (2008);
    arXiv:0804.1109
  21. Optimal phase estimation in quantum networks,
    Wim van Dam, G. Mauro D'Ariano, Artur Ekert, Chiara Macchiavello, and Michele Mosca,
    Journal of Physics A: Mathematical and Theoretical, Volume 40, pages 7971-7984 (2007);
    arXiv:0706.4412
  22. Quantum computing: In the 'death zone'?,
    Wim van Dam,
    Nature Physics, Volume 3, Number 4, pages 220-221 (2007)
    doi:10.1038/nphys585
  23. Optimal quantum circuits for general phase estimation,
    Wim van Dam, G. Mauro D'Ariano, Artur Ekert, Chiara Macchiavello, and Michele Mosca,
    Physical Review Letters, Volume 98, Number 9, Article 090501 (2007);
    arXiv:quant-ph/0609160
  24. Quantum algorithm for a generalized hidden shift problem,
    Andrew M. Childs and Wim van Dam,
    Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pages 1225-1234 (2007);
    arXiv:quant-ph/0507190
  25. From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups,
    Dave Bacon, Andrew M. Childs, and Wim van Dam,
    Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 469-478 (2005);
    arXiv:quant-ph/0504083
  26. Implausible Consequences of Superstrong Nonlocality,
    Wim van Dam,
    Natural Computing, Volume 12, Issue 1, pages 9-12, March 2013;
    arXiv:quant-ph/0501159
  27. Optimal measurements for the dihedral hidden subgroup problem,
    Dave Bacon, Andrew M. Childs, and Wim van Dam,
    Chicago Journal of Theoretical Computer Science, Article 2 (2006);
    arXiv:quant-ph/0501044
  28. Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation,
    Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev,
    updated version in SIAM Review, Volume 50, No. 4, pages 755-787 (2008)
    original version in SIAM Journal on Computing, Volume 37, Issue 1, pages 166-194 (2007)
    preliminary version in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pages 42-51 (2004);
    arXiv:quant-ph/0405098
  29. Quantum Computing and Zeroes of Zeta Functions,
    Wim van Dam,
    arXiv:quant-ph/0405081
  30. Summary of Delsarte's "Nombre de Solutions des Équations Polynomiales sur un Corps Fini",
    Wim van Dam,
    arXiv:math.HO/0401066
  31. Quantum Algorithms for Estimating Gauss Sums and Calculating Discrete Logarithms,
    Wim van Dam and Gadiel Seroussi (December 2003)
  32. Quantum Computing Discrete Logarithms with the Help of a Preprocessed State,
    Wim van Dam,
    arXiv:quant-ph/0311134
  33. Comment on "Quantum identification schemes with entanglements",
    Wim van Dam,
    Physical Review A, Volume 68, Number 2, Article 026301 (2003);
    arXiv:quant-ph/0307126
  34. The statistical strength of nonlocality proofs,
    Wim van Dam, Richard Gill and Peter Grünwald,
    IEEE Transactions on Information Theory, Volume 51, Issue 8, pages 2812-2835 (2005);
    arXiv:quant-ph/0307125
  35. Think Nonlocally (book review of Amir Aczel's "Entanglement: The Greatest Mystery in Physics"),
    Wim van Dam,
    American Scientist, Volume 91, No. 3 (May-June 2003)
  36. Experimental implementation of an adiabatic quantum optimization algorithm,
    Matthias Steffen, Wim van Dam, Tad Hogg, Greg Breyta and Isaac Chuang,
    Physical Review Letters, Volume 90, Number 6, Article 067903 (2003);
    arXiv:quant-ph/0302057
  37. Quantum Algorithms for some Hidden Shift Problems,
    Wim van Dam, Sean Hallgren and Lawrence Ip,
    SIAM Journal on Computing, Volume 36, Issue 3, pages 763-778 (2006);
    preliminary version in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pages 489-498 (2003);
    arXiv:quant-ph/0211140
  38. On Quantum Computation Theory,
    Wim van Dam,
    PhD thesis, University of Amsterdam, Department of Computer Science (October 2002)
  39. Efficient Quantum Algorithms for Estimating Gauss Sums,
    Wim van Dam and Gadiel Seroussi,
    arXiv:quant-ph/0207131
  40. Rényi-entropic bounds on quantum communication,
    Wim van Dam and Patrick Hayden,
    arXiv:quant-ph/0204093
  41. Universal entanglement transformations without communication,
    Wim van Dam and Patrick Hayden,
    Physical Review A, Rapid Communications, Volume 67, Issue 6, 060302(R) (2003);
    arXiv:quant-ph/0201041, under the title Embezzling Entangled Quantum States
  42. How Powerful is Adiabatic Quantum Computation?,
    Wim van Dam, Mike Mosca and Umesh Vazirani,
    Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS'01), pages 279-287 (2001);
    arXiv:quant-ph/0206003
  43. Efficient quantum algorithms for Shifted Quadratic Character Problems,
    Wim van Dam and Sean Hallgren,
    arXiv:quant-ph/0011067
  44. Quantum Algorithms for Weighing Matrices and Quadratic Residues,
    Wim van Dam,
    Algorithmica, Volume 34, No. 4, pages 413-428 (2002);
    arXiv:quant-ph/0008059
  45. Quantum Kolmogorov Complexity,
    André Berthiaume, Wim van Dam and Sophie Laplante,
    Journal of Computer and Systems Sciences, Volume 63, No. 2, September 2001, pages 201-221;
    preliminary version in Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pages 240-249 (2000);
    arXiv:quant-ph/0005018
  46. Physicists triumph at Guess my Number,
    Andrew Steane and Wim van Dam,
    Physics Today    , Volume 53(2), pages 35-39 (February 2000);
    doi:10.1063/1.882963
  47. Nonlocality & Communication Complexity,
    Wim van Dam,
    PhD thesis, University of Oxford, Department of Physics (2000)
  48. Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates,
    Wim van Dam, Frédéric Magniez, Michele Mosca and Miklos Santha,
    SIAM Journal on Computing, Volume 37, Issue 2, pages 611-629 (2007)
    preliminary version in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC'00), pages 688-696;
    arXiv:quant-ph/9904108
  49. Bounded Quantum Query Complexity,
    Harry Buhrman and Wim van Dam,
    Proceedings of the 14th Annual IEEE Conference on Computational Complexity (Complexity), pages 149-156 (1999);
    arXiv:quant-ph/9903035
  50. Two Classical Queries versus One Quantum Query,
    Wim van Dam,
    arXiv:quant-ph/9806090
    (This report is superseded by the article `Bounded Quantum Query Complexity' with Harry Buhrman.)
  51. Quantum communication using a nonlocal Zeno effect,
    Lucien Hardy and Wim van Dam,
    Physical Review A, Volume 59(4), pages 2635-2640, April 1999;
    arXiv:quant-ph/9805037, under the title Quantum Whispers
  52. Quantum Oracle Interrogation: Getting all information for almost half the price,
    Wim van Dam,
    Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS'98), pages 362-367;
    arXiv:quant-ph/9805006
  53. Multiparty Quantum Communication Complexity,
    Harry Buhrman, Wim van Dam, Peter Høyer and Alain Tapp,
    Physical Review A, Volume 60(4), pages 2737-2741, October 1999;
    arXiv:quant-ph/9710054
  54. Quantum Entanglement and the Communication Complexity of the Inner Product Function,
    Richard Cleve, Wim van Dam, Michael Nielsen and Alain Tapp,
    Quantum Computing and Quantum Communications, Proceedings of the 1st NASA International Conference, QCQC'98, Palm Springs, California, USA, February 17-20 (1998), Lecture Notes in Computer Science 1509, C.P. Williams (editor), pages 61-74;
    Theoretical Computer Science (2013), doi:10.1016/j.tcs.2012.12.012
    arXiv:quant-ph/9708019
  55. Quantum Entanglement and Communication Complexity,
    Harry Buhrman, Richard Cleve and Wim van Dam,
    SIAM Journal on Computing, Volume 30, Issue 6, pages 1829-1841 (2001);
    arXiv:quant-ph/9705033
  56. A Universal Quantum Cellular Automaton,
    Wim van Dam,
    Proceedings of PhysComp96, New England Complex Systems Institute, (editors: T.Toffoli, M.Biafore and J.Leão), pages 323-331, InterJournal manuscript no. 91 (November 1996)
  57. Quantum Cellular Automata,
    Wim van Dam, Master thesis, Department of Mathematics and Computer Science, University of Nijmegen, The Netherlands (August 1996)
    (A much more readable summary of this thesis is my PhysComp96 article above.)
last update: 2017-06-17 by vandam@ucb.edu