1. Krawtchouk polynomials and Krawtchouk matrices
Philip Feinsilver, Jerzy Kocik
Recent advances in applied probability, Springer-Verlag, October, 2004
http://arxiv.org/abs/quant-ph/0702073
Krawtchouk matrices have as entries values of the Krawtchouk polynomials for nonnegative integer arguments. We show how they arise as condensed Sylvester-Hadamard matrices via a binary shuffling function. The underlying symmetric tensor algebra is presented. Our approach is used to solve Kac' formulation of the Ehrenfest urn model. Connections with quantum and classical random walks are shown as well as various extensions of the classical polynomials.
2. A Quantum Algorithm for the Hamiltonian NAND Tree
E. Farhi, J. Goldstone, S. Gutmann
http://arxiv.org/abs/quant-ph/0702144
We give a quantum algorithm for the binary NAND tree problem in the Hamiltonian oracle model. The algorithm uses a continuous time quantum walk with a run time proportional to sqrt N. We also show a lower bound of sqrt N for the NAND tree problem in the Hamiltonian oracle model.
3. Discrete-query quantum algorithm for NAND trees
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, David Yeung
Theory of Computing, Vol. 5 (2009) 119-123
http://arxiv.org/abs/quant-ph/0702160
Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N^{1/2 + epsilon}) queries in the conventional quantum query model, for any fixed epsilon > 0.
4. Krawtchouk matrices from classical and quantum random walks
Philip Feinsilver, Jerzy Kocik
Contemporary Mathematics, Volume 287 (2001) 83-96
http://arxiv.org/abs/quant-ph/0702173
Krawtchouk's polynomials occur classically as orthogonal polynomials with respect to the binomial distribution. They may be also expressed in the form of matrices, that emerge as arrays of the values that the polynomials take. The algebraic properties of these matrices provide a very interesting and accessible example in the approach to probability theory known as quantum probability. First it is noted how the Krawtchouk matrices are connected to the classical symmetric Bernoulli random walk. And we show how to derive Krawtchouk matrices in the quantum probability context via tensor powers of the elementary Hadamard matrix. Then connections with the classical situation are shown by calculating expectation values in the quantum case.