A quantum computer is a device that uses a quantum mechanical representation of information to performcalculations. Information is stored in quantum bits, the states of which can be represented as `2-normalizedvectors in a complex vector space. For example, we can write the state of n qubits as|ψi =Xx∈{0,1}nax|xi (1.1)where the ax ∈ C satisfy Px|ax|2 = 1. We refer to the basis of states |xi as the computational basis.It will often be useful to think of quantum states as storing data in a more abstract form. For example,given a group G, we could write |gi for a basis state corresponding to the group element g ∈ G, and|φi =Xg∈Gbg|gi (1.2)for an arbitrary superposition over the group. We assume that there is some canonical way of efficientlyrepresenting group elements using bit strings; it is usually unnecessary to make this representation explicit.If a quantum computer stores the state |ψi and the state |φi, its overall state is given by the tensorproduct of those two states. This may be denoted |ψi ⊗ |φi = |ψi|φi = |ψ, φi.
However, a moments reection shows that this typically does not dene a unitary transformation, since corresponding to adjacent vertices j, k with a common neighbor (cid:96) evolve the orthogonal states to non-orthogonal states. We could potentially avoid this problem using a rule that sometimes introduces phases, but that would violate the spirit of dening a process that behaves in the same way at every vertex. In fact, even if we give that up, there are some graphs that simply do not allow local unitary dynamics . We can get around this diculty if we allow ourselves to enlarge the Hilbert space, an idea proposed by Watrous as part of a logarithmic-space quantum algorithm for deciding whether two vertices are connected in a graph . Let the Hilbert space consist of states of the form E. We can think of j, k | the walk as taking place on the (directed) edges of the graph; the state represents a walker at vertex j that will move toward vertex k. Each step of the walk consists of t
id: f252abcc2edcc241b00edcf8d492e3e1 - page: 85
First, we apply a unitary transformation that operates on the second register conditional on the rst register. This transformation is sometimes referred to as a coin ip, as it modies the next destination of the walker. A common choice is the Grover diusion operator over the neighbors of j, namely
id: c964c829005617dffe8c77c66b8f55f8 - page: 85
Next, the walker is moved to the vertex indicated in the second register. Of course, since the process must (17.1) (17.2) (17.3) 78 Chapter 17. Discrete-time quantum walk be unitary, the only way to do this is to swap the two registers using the operator S := (cid:88) (j,k) E j, k | (cid:105)(cid:104)
id: 4893b10ae417b1e8a43b2542d214244d - page: 85
(17.4) Overall, one step of the discrete-time quantum walk is described by the unitary operator SC. In principle, this construction can be used to dene a discrete-time quantum walk on any graph (although care must be taken if the graph is not regular). However, in practice it is often more convenient to use an alternative framework introduced by Szegedy , as described in the next section. 17.2 How to quantize a Markov chain A discrete-time classical random walk on an N -vertex graph can be represented by an N N matrix P . The entry Pkj represents the probability of making a transition to k from j, so that an initial probability RN becomes P p after one step of the walk. To preserve normalization, we must have distribution p (cid:80)N k=1 Pkj = 1 for any j For any N 1, . . . , N ; we say that such a matrix is stochastic. } { N stochastic matrix P (not necessarily symmetric), we can dene a corresponding discreteCN . To dene this walk, we introduce
id: aff21ca8cc93382b8ce15f20c1e4bc3f - page: 86