DOI: 10.1007/s00220-009-0930-1. On the Relationship Between Continuous- and Discrete-Time Quantum Walk

On the Relationship Between Continuous- and Discrete-Time Quantum Walk

10.1007/s00220-009-0930-1

Crossref journal-article

Springer Science and Business Media LLC

Communications in Mathematical Physics (297)

Bibliography

Childs, A. M. (2009). On the Relationship Between Continuous- and Discrete-Time Quantum Walk. Communications in Mathematical Physics, 294(2), 581â603.

Authors 1

Andrew M. Childs (first)

References 54 Referenced 264

Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51 (4) 595–605 (2004), preliminary versions in STOC 2002 and FOCS 2002 (10.1145/1008731.1008735)
Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proc. 33rd ACM Symposium on Theory of Computing, pp. 50–59, 2001, available at http://arxiv.org/abs/quant-ph/0012090 , 2000
Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical zero knowledge. In: Proc. 35th ACM Symposium on Theory of Computing, pp. 20–29, 2003, available at http://arxiv.org/abs/quant-ph/0301023 , 2003
Aldous, D., Fill, J.A.: Reversible Markov chains and random walks on graphs (in preparation), http://www.stat.berkeley.edu/~aldous/RWG/book.html
Ambainis A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007) (10.1137/S0097539705447311) / SIAM J. Comput. by A. Ambainis (2007)
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. Proc. 33rd ACM Symposium on Theory of Computing, pp. 37–49, 2001, available at http://arxiv.org/abs/quant-ph/0010117 , 2000
Ambainis, A., Childs, A.M., Reichardt, B.W., Špalek, R., Zhang S.: Any AND-OR formula of size N can be evaluated in time N 1/2+o(1) on a quantum computer. In: Proc. 48th IEEE Symposium on Foundations of Computer Science, pp. 363–372, 2007, available at http://arxiv.org/abs/quant-ph/0703015 and http://arxiv.org/abs/0704.3628 , 2007
Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1099–1108, 2005, available at http://arxiv.org/abs/quant-ph/0402107 , 2004
Berry D.W., Ahokas G., Cleve R., Sanders B.C.: Efficient quantum algorithms for simulating sparse Hamiltonians. Commun. Math. Phys. 270(2), 359–371 (2007) (10.1007/s00220-006-0150-x) / Commun. Math. Phys. by D.W. Berry (2007)
Buhrman, H., Špalek, R.: Quantum verification of matrix products. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 880–889, 2006, available at http://arxiv.org/abs/quant-ph/0409035 , 2004
Bužek V., Derka R., Massar S.: Optimal quantum clocks. Phys. Rev. Lett. 82(10), 2207–2210 (1999) (10.1103/PhysRevLett.82.2207) / Phys. Rev. Lett. by V. Bužek (1999)
Childs, A.M.: Quantum information processing in continuous time. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 2004
Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by quantum walk. In: Proc. 35th ACM Symposium on Theory of Computing, pp. 59–68, 2003, available at http://arxiv.org/abs/quant-ph/0209131 , 2002
Childs A.M., Eisenberg J.M.: Quantum algorithms for subset finding. Quant. Inf. Comp. 5(7), 593–604 (2005) / Quant. Inf. Comp. by A.M. Childs (2005)
Childs A.M., Farhi E., Gutmann S.: An example of the difference between quantum and classical random walks. Quant. Inf. Proc. 1(1-2), 35–43 (2002) (10.1023/A:1019609420309) / Quant. Inf. Proc. by A.M. Childs (2002)
Childs A.M., Goldstone J.: Spatial search by quantum walk. Phys. Rev. A 70(2), 022314 (2004) (10.1103/PhysRevA.70.022314) / Phys. Rev. A by A.M. Childs (2004)
Childs A.M., Goldstone J.: Spatial search and the Dirac equation. Phys. Rev. A 70(4), 042312 (2004) (10.1103/PhysRevA.70.042312) / Phys. Rev. A by A.M. Childs (2004)
Childs, A.M., Schulman, L.J., Vazirani, U.V.: Quantum algorithms for hidden nonlinear structures. In: Proc. 48th IEEE Symposium on Foundations of Computer Science, pp. 395–404, 2007, available at http://arxiv.org/abs/0705.2784 , 2007
Cleve, R., Gottesman, D., Mosca, M., Somma, R.D., Yonge-Mallo, D.L.: Efficient discrete-time simulations of continuous-time quantum query algorithms. In: Proc. 41st ACM Symposium on Theory of Computing, pp. 409–416, 2009, available at http://arxiv.org/abs/0811.4428 , 2008
van Dam W., D’Ariano G.M., Ekert A., Macchiavello C., Mosca M.: Optimal phase estimation in quantum networks. J. Phys. A 40(28), 7971–7984 (2007) (10.1088/1751-8113/40/28/S07) / J. Phys. A by W. Dam van (2007)
van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, pp. 489–498, 2002, available at http://arxiv.org/abs/quant-ph/0211140 , 2002
van Dam, W., Mosca, M., Vazirani, U.: How powerful is adiabatic quantum computation?. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science, pp. 279–287, 2001, available at http://arxiv.org/abs/quant-ph/0206003 , 2002
van Dam, W., Seroussi, G.: Quantum algorithms for estimating Gauss sums and calculating discrete logarithms. Manuscript, 2003, available at http://www.cs.ucsb.edu/~vandam/gausssumdlog.pdf
Damgård, I.B.: On the randomness of Legendre and Jacobi sequences. Advances in Cryptology - CRYPTO ’88, Lecture Notes in Computer Science, vol. 403, New York: Springer, 1990, pp. 163–172
Farhi E., Goldstone J., Gutmann S.: A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing 4(1), 169–190 (2008) (10.4086/toc.2008.v004a008) / Theory of Computing by E. Farhi (2008)
Farhi E., Gutmann S.: Analog analogue of a digital quantum computation. Phys. Rev. A 57(4), 2403–2406 (1998) (10.1103/PhysRevA.57.2403) / Phys. Rev. A by E. Farhi (1998)
Farhi E., Gutmann S.: Quantum computation and decision trees. Phys. Rev. A 58(2), 915–928 (1998) (10.1103/PhysRevA.58.915) / Phys. Rev. A by E. Farhi (1998)
Godsil, C.: Association schemes. Lecture notes, available at http://quoll.uwaterloo.ca/pstuff/assoc.pdf , 2004
Grover, L., Rudolph, T.: Creating superpositions that correspond to efficiently integrable probability distributions, available at http://arxiv.org/abs/quant-ph/0208112v1 , 2002
Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325–328 (1997), preliminary version in STOC 1996 (10.1103/PhysRevLett.79.325)
Kedlaya K.S.: Quantum computation of zeta functions of curves. Comput. Complex. 15(1), 1–19 (2006) (10.1007/s00037-006-0204-7) / Comput. Complex. by K.S. Kedlaya (2006)
Linial N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992) (10.1137/0221015) / SIAM J. Comput. by N. Linial (1992)
Lloyd S.: Universal quantum simulators. Science 273(5278), 1073–1078 (1996) (10.1126/science.273.5278.1073) / Science by S. Lloyd (1996)
Luis A., Peřina J.: Optimum phase-shift estimation and the quantum description of the phase difference. Phys. Rev. A 54(5), 4564–4570 (1996) (10.1103/PhysRevA.54.4564) / Phys. Rev. A by A. Luis (1996)
Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. Algorithmica 48(3), 221–232 (2007), preliminary version in ICALP 2005 (10.1007/s00453-007-0057-8)
Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proc. 39th ACM Symposium on Theory of Computing, pp. 575–584, 2007, available at http://arvix.org/abs/quant-ph/0608026 , 2006
Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1109–1117, 2005, available at http://arxiv.org/abs/quant-ph/0310134 , 2003
Meyer D.A.: From quantum cellular automata to quantum lattice gasses. J. Stat. Phys. 85(5/6), 551–574 (1996) (10.1007/BF02199356) / J. Stat. Phys. by D.A. Meyer (1996)
Meyer D.A.: On the absence of homogeneous scalar unitary cellular automata. Phys. Lett. A 223, 337–340 (1996) (10.1016/S0375-9601(96)00745-1) / Phys. Lett. A by D.A. Meyer (1996)
Mochon C.: Hamiltonian oracles. Phys. Rev. A 75(4), 042313 (2007) (10.1103/PhysRevA.75.042313) / Phys. Rev. A by C. Mochon (2007)
Moore, C., Russell, A.: Quantum walks on the hypercube. In: Proc. 6th International Workshop on Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science, Vol. 2483, Berlin: Springer, 2002 pp. 164–178 (10.1007/3-540-45726-7_14)
Regev, O.: Witness-preserving amplification of QMA. Lecture notes, http://www.cs.tau.ac.il/~odedr/teaching/quantum_fall_2005/ln/qma.pdf , 2006
Reichardt, B.W., Špalek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proc. 40th ACM Symposium on Theory of Computing, pp. 103–112, 2008, available at http://arxiv.org/abs/0710.2630 , 2007
Roland J., Cerf N.J.: Quantum search by local adiabatic evolution. Phys. Rev. A 65(4), 042308 (2002) (10.1103/PhysRevA.65.042308) / Phys. Rev. A by J. Roland (2002)
Roland J., Cerf N.J.: Quantum-circuit model of Hamiltonian search algorithms. Phys. Rev. A 68(6), 062311 (2003) (10.1103/PhysRevA.68.062311) / Phys. Rev. A by J. Roland (2003)
Schmidt W.M.: Equations over Finite Fields: An Elementary Approach. 2nd ed. Kendrick Press, Hebercity, UT (2004) / Equations over Finite Fields: An Elementary Approach by W.M. Schmidt (2004)
Severini S.: On the digraph of a unitary matrix. SIAM J. Matrix Anal. Appl. 25(1), 295–300 (2003) (10.1137/S0895479802410293) / SIAM J. Matrix Anal. Appl. by S. Severini (2003)
Shenvi N., Kempe J., Whaley K.B.: A quantum random walk search algorithm. Phys. Rev. A 67(5), 052307 (2003) (10.1103/PhysRevA.67.052307) / Phys. Rev. A by N. Shenvi (2003)
Shor P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997) (10.1137/S0097539795293172) / SIAM J. Comput. by P.W. Shor (1997)
Strauch F.W.: Connecting the discrete- and continuous-time quantum walks. Phys. Rev. A 74(3), 030301 (2006) (10.1103/PhysRevA.74.030301) / Phys. Rev. A by F.W. Strauch (2006)
Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proc. 45th IEEE Symposium on Foundations of Computer Science, pp. 32–41, 2004, available at http://arxiv.org/abs/quant-ph/0401053 , 2004
Tulsi A.: Faster quantum-walk algorithm for the two-dimensional spatial search. Phys. Rev. A 78(1), 012310 (2008) (10.1103/PhysRevA.78.012310) / Phys. Rev. A by A. Tulsi (2008)
Watrous J.: Quantum simulations of classical random walks and undirected graph connectivity. J. Comput. System Sci. 62(2), 376–391 (2001) (10.1006/jcss.2000.1732) / J. Comput. System Sci. by J. Watrous (2001)
Weil A.: On some exponential sums. Proc. Natl. Acad. Sci. 34(5), 204–207 (1948) (10.1073/pnas.34.5.204) / Proc. Natl. Acad. Sci. by A. Weil (1948)

Dates

Type	When
Created	15 years, 10 months ago (Oct. 9, 2009, 4:59 p.m.)
Deposited	6 years, 3 months ago (May 24, 2019, 6:56 a.m.)
Indexed	2 weeks, 3 days ago (Aug. 19, 2025, 6:22 a.m.)
Issued	15 years, 10 months ago (Oct. 10, 2009)
Published	15 years, 10 months ago (Oct. 10, 2009)
Published Online	15 years, 10 months ago (Oct. 10, 2009)
Published Print	15 years, 6 months ago (March 1, 2010)

Funders 0

None

BibTeX

@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} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        19
      ]
    ],
    "date-time": "2025-08-19T10:22:10Z",
    "timestamp": 1755598930271
  },
  "reference-count": 54,
  "publisher": "Springer Science and Business Media LLC",
  "issue": "2",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2009,
            10,
            10
          ]
        ],
        "date-time": "2009-10-10T00:00:00Z",
        "timestamp": 1255132800000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "http://www.springer.com/tdm"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        2010,
        3
      ]
    ]
  },
  "DOI": "10.1007/s00220-009-0930-1",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2009,
        10,
        9
      ]
    ],
    "date-time": "2009-10-09T20:59:46Z",
    "timestamp": 1255121986000
  },
  "page": "581-603",
  "source": "Crossref",
  "is-referenced-by-count": 264,
  "title": "On the Relationship Between Continuous- and Discrete-Time Quantum Walk",
  "prefix": "10.1007",
  "volume": "294",
  "author": [
    {
      "given": "Andrew M.",
      "family": "Childs",
      "sequence": "first",
      "affiliation": []
    }
  ],
  "member": "297",
  "published-online": {
    "date-parts": [
      [
        2009,
        10,
        10
      ]
    ]
  },
  "reference": [
    {
      "key": "930_CR1",
      "doi-asserted-by": "crossref",
      "unstructured": "Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51 (4) 595\u2013605 (2004), preliminary versions in STOC 2002 and FOCS 2002",
      "DOI": "10.1145/1008731.1008735"
    },
    {
      "key": "930_CR2",
      "unstructured": "Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proc. 33rd ACM Symposium on Theory of Computing, pp. 50\u201359, 2001, available at http://arxiv.org/abs/quant-ph/0012090 , 2000"
    },
    {
      "key": "930_CR3",
      "unstructured": "Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical zero knowledge. In: Proc. 35th ACM Symposium on Theory of Computing, pp. 20\u201329, 2003, available at http://arxiv.org/abs/quant-ph/0301023 , 2003"
    },
    {
      "key": "930_CR4",
      "unstructured": "Aldous, D., Fill, J.A.: Reversible Markov chains and random walks on graphs (in preparation), http://www.stat.berkeley.edu/~aldous/RWG/book.html"
    },
    {
      "issue": "1",
      "key": "930_CR5",
      "doi-asserted-by": "crossref",
      "first-page": "210",
      "DOI": "10.1137/S0097539705447311",
      "volume": "37",
      "author": "A. Ambainis",
      "year": "2007",
      "unstructured": "Ambainis A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210\u2013239 (2007)",
      "journal-title": "SIAM J. Comput."
    },
    {
      "key": "930_CR6",
      "unstructured": "Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. Proc. 33rd ACM Symposium on Theory of Computing, pp. 37\u201349, 2001, available at http://arxiv.org/abs/quant-ph/0010117 , 2000"
    },
    {
      "key": "930_CR7",
      "unstructured": "Ambainis, A., Childs, A.M., Reichardt, B.W., \u0160palek, R., Zhang S.: Any AND-OR formula of size N can be evaluated in time N 1/2+o(1) on a quantum computer. In: Proc. 48th IEEE Symposium on Foundations of Computer Science, pp. 363\u2013372, 2007, available at http://arxiv.org/abs/quant-ph/0703015 and http://arxiv.org/abs/0704.3628 , 2007"
    },
    {
      "key": "930_CR8",
      "unstructured": "Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1099\u20131108, 2005, available at http://arxiv.org/abs/quant-ph/0402107 , 2004"
    },
    {
      "issue": "2",
      "key": "930_CR9",
      "doi-asserted-by": "crossref",
      "first-page": "359",
      "DOI": "10.1007/s00220-006-0150-x",
      "volume": "270",
      "author": "D.W. Berry",
      "year": "2007",
      "unstructured": "Berry D.W., Ahokas G., Cleve R., Sanders B.C.: Efficient quantum algorithms for simulating sparse Hamiltonians. Commun. Math. Phys. 270(2), 359\u2013371 (2007)",
      "journal-title": "Commun. Math. Phys."
    },
    {
      "key": "930_CR10",
      "unstructured": "Buhrman, H., \u0160palek, R.: Quantum verification of matrix products. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 880\u2013889, 2006, available at http://arxiv.org/abs/quant-ph/0409035 , 2004"
    },
    {
      "issue": "10",
      "key": "930_CR11",
      "doi-asserted-by": "crossref",
      "first-page": "2207",
      "DOI": "10.1103/PhysRevLett.82.2207",
      "volume": "82",
      "author": "V. Bu\u017eek",
      "year": "1999",
      "unstructured": "Bu\u017eek V., Derka R., Massar S.: Optimal quantum clocks. Phys. Rev. Lett. 82(10), 2207\u20132210 (1999)",
      "journal-title": "Phys. Rev. Lett."
    },
    {
      "key": "930_CR12",
      "unstructured": "Childs, A.M.: Quantum information processing in continuous time. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 2004"
    },
    {
      "key": "930_CR13",
      "unstructured": "Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by quantum walk. In: Proc. 35th ACM Symposium on Theory of Computing, pp. 59\u201368, 2003, available at http://arxiv.org/abs/quant-ph/0209131 , 2002"
    },
    {
      "issue": "7",
      "key": "930_CR14",
      "first-page": "593",
      "volume": "5",
      "author": "A.M. Childs",
      "year": "2005",
      "unstructured": "Childs A.M., Eisenberg J.M.: Quantum algorithms for subset finding. Quant. Inf. Comp. 5(7), 593\u2013604 (2005)",
      "journal-title": "Quant. Inf. Comp."
    },
    {
      "issue": "1-2",
      "key": "930_CR15",
      "doi-asserted-by": "crossref",
      "first-page": "35",
      "DOI": "10.1023/A:1019609420309",
      "volume": "1",
      "author": "A.M. Childs",
      "year": "2002",
      "unstructured": "Childs A.M., Farhi E., Gutmann S.: An example of the difference between quantum and classical random walks. Quant. Inf. Proc. 1(1-2), 35\u201343 (2002)",
      "journal-title": "Quant. Inf. Proc."
    },
    {
      "issue": "2",
      "key": "930_CR16",
      "doi-asserted-by": "crossref",
      "first-page": "022314",
      "DOI": "10.1103/PhysRevA.70.022314",
      "volume": "70",
      "author": "A.M. Childs",
      "year": "2004",
      "unstructured": "Childs A.M., Goldstone J.: Spatial search by quantum walk. Phys. Rev. A 70(2), 022314 (2004)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "issue": "4",
      "key": "930_CR17",
      "doi-asserted-by": "crossref",
      "first-page": "042312",
      "DOI": "10.1103/PhysRevA.70.042312",
      "volume": "70",
      "author": "A.M. Childs",
      "year": "2004",
      "unstructured": "Childs A.M., Goldstone J.: Spatial search and the Dirac equation. Phys. Rev. A 70(4), 042312 (2004)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "930_CR18",
      "unstructured": "Childs, A.M., Schulman, L.J., Vazirani, U.V.: Quantum algorithms for hidden nonlinear structures. In: Proc. 48th IEEE Symposium on Foundations of Computer Science, pp. 395\u2013404, 2007, available at http://arxiv.org/abs/0705.2784 , 2007"
    },
    {
      "key": "930_CR19",
      "unstructured": "Cleve, R., Gottesman, D., Mosca, M., Somma, R.D., Yonge-Mallo, D.L.: Efficient discrete-time simulations of continuous-time quantum query algorithms. In: Proc. 41st ACM Symposium on Theory of Computing, pp. 409\u2013416, 2009, available at http://arxiv.org/abs/0811.4428 , 2008"
    },
    {
      "issue": "28",
      "key": "930_CR20",
      "doi-asserted-by": "crossref",
      "first-page": "7971",
      "DOI": "10.1088/1751-8113/40/28/S07",
      "volume": "40",
      "author": "W. Dam van",
      "year": "2007",
      "unstructured": "van Dam W., D\u2019Ariano G.M., Ekert A., Macchiavello C., Mosca M.: Optimal phase estimation in quantum networks. J. Phys. A 40(28), 7971\u20137984 (2007)",
      "journal-title": "J. Phys. A"
    },
    {
      "key": "930_CR21",
      "unstructured": "van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, pp. 489\u2013498, 2002, available at http://arxiv.org/abs/quant-ph/0211140 , 2002"
    },
    {
      "key": "930_CR22",
      "unstructured": "van Dam, W., Mosca, M., Vazirani, U.: How powerful is adiabatic quantum computation?. In: Proc. 42nd IEEE Symposium on Foundations of Computer Science, pp. 279\u2013287, 2001, available at http://arxiv.org/abs/quant-ph/0206003 , 2002"
    },
    {
      "key": "930_CR23",
      "unstructured": "van Dam, W., Seroussi, G.: Quantum algorithms for estimating Gauss sums and calculating discrete logarithms. Manuscript, 2003, available at http://www.cs.ucsb.edu/~vandam/gausssumdlog.pdf"
    },
    {
      "key": "930_CR24",
      "unstructured": "Damg\u00e5rd, I.B.: On the randomness of Legendre and Jacobi sequences. Advances in Cryptology - CRYPTO \u201988, Lecture Notes in Computer Science, vol. 403, New York: Springer, 1990, pp. 163\u2013172"
    },
    {
      "issue": "1",
      "key": "930_CR25",
      "doi-asserted-by": "crossref",
      "first-page": "169",
      "DOI": "10.4086/toc.2008.v004a008",
      "volume": "4",
      "author": "E. Farhi",
      "year": "2008",
      "unstructured": "Farhi E., Goldstone J., Gutmann S.: A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing 4(1), 169\u2013190 (2008)",
      "journal-title": "Theory of Computing"
    },
    {
      "issue": "4",
      "key": "930_CR26",
      "doi-asserted-by": "crossref",
      "first-page": "2403",
      "DOI": "10.1103/PhysRevA.57.2403",
      "volume": "57",
      "author": "E. Farhi",
      "year": "1998",
      "unstructured": "Farhi E., Gutmann S.: Analog analogue of a digital quantum computation. Phys. Rev. A 57(4), 2403\u20132406 (1998)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "issue": "2",
      "key": "930_CR27",
      "doi-asserted-by": "crossref",
      "first-page": "915",
      "DOI": "10.1103/PhysRevA.58.915",
      "volume": "58",
      "author": "E. Farhi",
      "year": "1998",
      "unstructured": "Farhi E., Gutmann S.: Quantum computation and decision trees. Phys. Rev. A 58(2), 915\u2013928 (1998)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "930_CR28",
      "unstructured": "Godsil, C.: Association schemes. Lecture notes, available at http://quoll.uwaterloo.ca/pstuff/assoc.pdf , 2004"
    },
    {
      "key": "930_CR29",
      "unstructured": "Grover, L., Rudolph, T.: Creating superpositions that correspond to efficiently integrable probability distributions, available at http://arxiv.org/abs/quant-ph/0208112v1 , 2002"
    },
    {
      "key": "930_CR30",
      "doi-asserted-by": "crossref",
      "unstructured": "Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325\u2013328 (1997), preliminary version in STOC 1996",
      "DOI": "10.1103/PhysRevLett.79.325"
    },
    {
      "issue": "1",
      "key": "930_CR31",
      "doi-asserted-by": "crossref",
      "first-page": "1",
      "DOI": "10.1007/s00037-006-0204-7",
      "volume": "15",
      "author": "K.S. Kedlaya",
      "year": "2006",
      "unstructured": "Kedlaya K.S.: Quantum computation of zeta functions of curves. Comput. Complex. 15(1), 1\u201319 (2006)",
      "journal-title": "Comput. Complex."
    },
    {
      "issue": "1",
      "key": "930_CR32",
      "doi-asserted-by": "crossref",
      "first-page": "193",
      "DOI": "10.1137/0221015",
      "volume": "21",
      "author": "N. Linial",
      "year": "1992",
      "unstructured": "Linial N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)",
      "journal-title": "SIAM J. Comput."
    },
    {
      "issue": "5278",
      "key": "930_CR33",
      "doi-asserted-by": "crossref",
      "first-page": "1073",
      "DOI": "10.1126/science.273.5278.1073",
      "volume": "273",
      "author": "S. Lloyd",
      "year": "1996",
      "unstructured": "Lloyd S.: Universal quantum simulators. Science 273(5278), 1073\u20131078 (1996)",
      "journal-title": "Science"
    },
    {
      "issue": "5",
      "key": "930_CR34",
      "doi-asserted-by": "crossref",
      "first-page": "4564",
      "DOI": "10.1103/PhysRevA.54.4564",
      "volume": "54",
      "author": "A. Luis",
      "year": "1996",
      "unstructured": "Luis A., Pe\u0159ina J.: Optimum phase-shift estimation and the quantum description of the phase difference. Phys. Rev. A 54(5), 4564\u20134570 (1996)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "930_CR35",
      "doi-asserted-by": "crossref",
      "unstructured": "Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. Algorithmica 48(3), 221\u2013232 (2007), preliminary version in ICALP 2005",
      "DOI": "10.1007/s00453-007-0057-8"
    },
    {
      "key": "930_CR36",
      "unstructured": "Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proc. 39th ACM Symposium on Theory of Computing, pp. 575\u2013584, 2007, available at http://arvix.org/abs/quant-ph/0608026 , 2006"
    },
    {
      "key": "930_CR37",
      "unstructured": "Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1109\u20131117, 2005, available at http://arxiv.org/abs/quant-ph/0310134 , 2003"
    },
    {
      "issue": "5/6",
      "key": "930_CR38",
      "doi-asserted-by": "crossref",
      "first-page": "551",
      "DOI": "10.1007/BF02199356",
      "volume": "85",
      "author": "D.A. Meyer",
      "year": "1996",
      "unstructured": "Meyer D.A.: From quantum cellular automata to quantum lattice gasses. J. Stat. Phys. 85(5/6), 551\u2013574 (1996)",
      "journal-title": "J. Stat. Phys."
    },
    {
      "key": "930_CR39",
      "doi-asserted-by": "crossref",
      "first-page": "337",
      "DOI": "10.1016/S0375-9601(96)00745-1",
      "volume": "223",
      "author": "D.A. Meyer",
      "year": "1996",
      "unstructured": "Meyer D.A.: On the absence of homogeneous scalar unitary cellular automata. Phys. Lett. A 223, 337\u2013340 (1996)",
      "journal-title": "Phys. Lett. A"
    },
    {
      "issue": "4",
      "key": "930_CR40",
      "doi-asserted-by": "crossref",
      "first-page": "042313",
      "DOI": "10.1103/PhysRevA.75.042313",
      "volume": "75",
      "author": "C. Mochon",
      "year": "2007",
      "unstructured": "Mochon C.: Hamiltonian oracles. Phys. Rev. A 75(4), 042313 (2007)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "930_CR41",
      "doi-asserted-by": "crossref",
      "unstructured": "Moore, C., Russell, A.: Quantum walks on the hypercube. In: Proc. 6th International Workshop on Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science, Vol. 2483, Berlin: Springer, 2002\u00a0pp. 164\u2013178",
      "DOI": "10.1007/3-540-45726-7_14"
    },
    {
      "key": "930_CR42",
      "unstructured": "Regev, O.: Witness-preserving amplification of QMA. Lecture notes, http://www.cs.tau.ac.il/~odedr/teaching/quantum_fall_2005/ln/qma.pdf , 2006"
    },
    {
      "key": "930_CR43",
      "unstructured": "Reichardt, B.W., \u0160palek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proc. 40th ACM Symposium on Theory of Computing, pp. 103\u2013112, 2008, available at http://arxiv.org/abs/0710.2630 , 2007"
    },
    {
      "issue": "4",
      "key": "930_CR44",
      "doi-asserted-by": "crossref",
      "first-page": "042308",
      "DOI": "10.1103/PhysRevA.65.042308",
      "volume": "65",
      "author": "J. Roland",
      "year": "2002",
      "unstructured": "Roland J., Cerf N.J.: Quantum search by local adiabatic evolution. Phys. Rev. A 65(4), 042308 (2002)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "issue": "6",
      "key": "930_CR45",
      "doi-asserted-by": "crossref",
      "first-page": "062311",
      "DOI": "10.1103/PhysRevA.68.062311",
      "volume": "68",
      "author": "J. Roland",
      "year": "2003",
      "unstructured": "Roland J., Cerf N.J.: Quantum-circuit model of Hamiltonian search algorithms. Phys. Rev. A 68(6), 062311 (2003)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "930_CR46",
      "volume-title": "Equations over Finite Fields: An Elementary Approach",
      "author": "W.M. Schmidt",
      "year": "2004",
      "unstructured": "Schmidt W.M.: Equations over Finite Fields: An Elementary Approach. 2nd ed. Kendrick Press, Hebercity, UT (2004)",
      "edition": "2"
    },
    {
      "issue": "1",
      "key": "930_CR47",
      "doi-asserted-by": "crossref",
      "first-page": "295",
      "DOI": "10.1137/S0895479802410293",
      "volume": "25",
      "author": "S. Severini",
      "year": "2003",
      "unstructured": "Severini S.: On the digraph of a unitary matrix. SIAM J. Matrix Anal. Appl. 25(1), 295\u2013300 (2003)",
      "journal-title": "SIAM J. Matrix Anal. Appl."
    },
    {
      "issue": "5",
      "key": "930_CR48",
      "doi-asserted-by": "crossref",
      "first-page": "052307",
      "DOI": "10.1103/PhysRevA.67.052307",
      "volume": "67",
      "author": "N. Shenvi",
      "year": "2003",
      "unstructured": "Shenvi N., Kempe J., Whaley K.B.: A quantum random walk search algorithm. Phys. Rev. A 67(5), 052307 (2003)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "issue": "5",
      "key": "930_CR49",
      "doi-asserted-by": "crossref",
      "first-page": "1484",
      "DOI": "10.1137/S0097539795293172",
      "volume": "26",
      "author": "P.W. Shor",
      "year": "1997",
      "unstructured": "Shor P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997)",
      "journal-title": "SIAM J. Comput."
    },
    {
      "issue": "3",
      "key": "930_CR50",
      "doi-asserted-by": "crossref",
      "first-page": "030301",
      "DOI": "10.1103/PhysRevA.74.030301",
      "volume": "74",
      "author": "F.W. Strauch",
      "year": "2006",
      "unstructured": "Strauch F.W.: Connecting the discrete- and continuous-time quantum walks. Phys. Rev. A 74(3), 030301 (2006)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "key": "930_CR51",
      "unstructured": "Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proc. 45th IEEE Symposium on Foundations of Computer Science, pp. 32\u201341, 2004, available at http://arxiv.org/abs/quant-ph/0401053 , 2004"
    },
    {
      "issue": "1",
      "key": "930_CR52",
      "doi-asserted-by": "crossref",
      "first-page": "012310",
      "DOI": "10.1103/PhysRevA.78.012310",
      "volume": "78",
      "author": "A. Tulsi",
      "year": "2008",
      "unstructured": "Tulsi A.: Faster quantum-walk algorithm for the two-dimensional spatial search. Phys. Rev. A 78(1), 012310 (2008)",
      "journal-title": "Phys. Rev. A"
    },
    {
      "issue": "2",
      "key": "930_CR53",
      "doi-asserted-by": "crossref",
      "first-page": "376",
      "DOI": "10.1006/jcss.2000.1732",
      "volume": "62",
      "author": "J. Watrous",
      "year": "2001",
      "unstructured": "Watrous J.: Quantum simulations of classical random walks and undirected graph connectivity. J. Comput. System Sci. 62(2), 376\u2013391 (2001)",
      "journal-title": "J. Comput. System Sci."
    },
    {
      "issue": "5",
      "key": "930_CR54",
      "doi-asserted-by": "crossref",
      "first-page": "204",
      "DOI": "10.1073/pnas.34.5.204",
      "volume": "34",
      "author": "A. Weil",
      "year": "1948",
      "unstructured": "Weil A.: On some exponential sums. Proc. Natl. Acad. Sci. 34(5), 204\u2013207 (1948)",
      "journal-title": "Proc. Natl. Acad. Sci."
    }
  ],
  "container-title": "Communications in Mathematical Physics",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/s00220-009-0930-1.pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "http://link.springer.com/article/10.1007/s00220-009-0930-1/fulltext.html",
      "content-type": "text/html",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/s00220-009-0930-1",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2019,
        5,
        24
      ]
    ],
    "date-time": "2019-05-24T10:56:09Z",
    "timestamp": 1558695369000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://link.springer.com/10.1007/s00220-009-0930-1"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2009,
        10,
        10
      ]
    ]
  },
  "references-count": 54,
  "journal-issue": {
    "issue": "2",
    "published-print": {
      "date-parts": [
        [
          2010,
          3
        ]
      ]
    }
  },
  "alternative-id": [
    "930"
  ],
  "URL": "http://dx.doi.org/10.1007/s00220-009-0930-1",
  "relation": {},
  "ISSN": [
    "0010-3616",
    "1432-0916"
  ],
  "subject": [],
  "container-title-short": "Commun. Math. Phys.",
  "published": {
    "date-parts": [
      [
        2009,
        10,
        10
      ]
    ]
  }
}