Continuous-Time Quantum Walks

In this page a Hamiltonian is a self-adjoint endomorphism $H$ of a finite-dimensional complex inner-product space $V$; no physical postulate is part of the term. Let $\sigma (H)$ be the set of its distinct eigenvalues and let $P_{\lambda }$ be the orthogonal projection onto the $\lambda$-eigenspace. For real time $t$, define the finite matrix evolution

$U_H(t):={\sum }_{\lambda \in \sigma (H)}{e}^{-it\lambda }{P}_{\lambda }=f_t(H),f_t(\lambda )=e^{-it\lambda }\mathrm{.}$

The second expression uses the finite spectral functional calculus The spectral functional calculus f(T) for a normal endomorphism. If $V$ is the zero space, the spectrum is empty and the empty sum is the unique endomorphism, which is also the identity on $V$. This definition specifies a mathematical unitary from a finite matrix; it makes no claim that the operation has an efficient circuit or a free access cost.

Let $H$ be a self-adjoint endomorphism of a finite-dimensional complex inner-product space $V$. For real $t,s$, the evolution from Finite Hermitian matrix dynamics satisfies $U_H(0)=I_V,U_H(t{)}^{\ast }{U}_H(t)=I_V,U_H(t+s)=U_H(t)U_H(s),\frac{d}{dt}{U}_H(t)=-iH{U}_H(t)\mathrm{.}$ Moreover, $U_H$ is the unique differentiable map $Y:\mathbb{R}\to \mathrm{End}(V)$ satisfying $Y^{\mathrm{\prime }}(t)=-iHY(t)$ and $Y(0)=I_V$.

For an integer $n\ge 0$, give each factor of the ordered register $V_n=({\mathbb{C}}^2{)}^{\otimes n}$ the basis $(e_0,e_1)$ and define the one-qubit matrix $H:=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\mathrm{.}$ Then $H$ is unitary and $H^{\otimes n}{e}_{0^n}=2^{-n\mathrm{/}2}{\sum }_{x\in \{0,1{\}}^n}{e}_x\mathrm{.}$ For $n=0$, the tensor product is $\mathbb{C}$, the empty word is the sole basis label, and $H^{\otimes 0}$ is the identity. The preparation uses exactly $n$ one-qubit $H$ gates when $H$ is primitive in the declared circuit model; otherwise its implementation and synthesis costs must be supplied there.

Let $V$ be a finite vertex set with a fixed order and let $w:V\times V\to [0,\mathrm{\infty })$ be symmetric. Self-loops are allowed and their weight is counted once in each row sum. On ${\mathbb{C}}^V$ with ordered basis $(e_v{)}_{v\in V}$, define the weighted adjacency matrix by $A_{uv}=w(u,v)$, the degree $d(v)={\sum }_{u\in V}w(v,u)$, and $D_{vv}=d(v)$ with all off-diagonal entries zero. The positive Laplacian is $L_{+}=D-A$; the other common sign convention is $L_{-}=A-D=-L_{+}$. A walk generator records the chosen edge weights, loop convention, basis order, and one of these signs. It is not a discrete transition matrix.

When every $d(v)>0$, the normalized adjacency is the separately defined matrix $A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}=D^{-1\mathrm{/}2}A{D}^{-1\mathrm{/}2}$. No normalized-adjacency operation is defined here at zero-degree vertices. The matrices $A,D,L_{+},L_{-}$ are Hermitian: $A_{vu}=w(v,u)=w(u,v)=\overline{A_{uv}}$ and $D$ is real diagonal. Under the positive-degree condition, $D^{-1\mathrm{/}2}$ is also real diagonal, so $A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}^{\ast }=A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}$. A zero-vertex graph gives the zero coordinate space and empty matrices; a quantum-walk input separately requires a normalized state, so it has no instance on that space.

Let $H$ be a self-adjoint endomorphism of a nonzero finite-dimensional complex-inner-product space $V$, let $t\in \mathbb{R}$, and let $[\psi ]$ be a pure state with a specified unit representative $\psi \in V$. The continuous-time quantum walk generated by $H$ at time $t$ has state vector

$\varphi (t):=U_H(t)\psi ,$

where $U_H(t)$ is the finite matrix evolution in Finite Hermitian matrix dynamics. By Unitary and differential identities for finite matrix dynamics, $U_H(t)$ is unitary, so $\varphi (t)$ is still a unit vector and its output pure-state ray is $[U_H(t)\psi ]$. This ray does not depend on the chosen unit representative: if ${\psi }^{\mathrm{\prime }}=\alpha \psi$ with $\mathrm{\mid }\alpha \mathrm{\mid }=1$, linearity gives $U_H(t){\psi }^{\mathrm{\prime }}=\alpha U_H(t)\psi$, the same ray. For a graph walk, $V$ is the ordered vertex register and $H$ is a separately specified Hermitian generator such as one of the matrices in Graph adjacency and Laplacian generator conventions. The definition alone supplies no circuit, Hamiltonian oracle, or efficiency claim.

Let $V$ be a nonzero finite-dimensional complex inner-product space, let $(e_y{)}_{y\in Y}$ be a finite orthonormal basis, and let $\varphi \in V$ be a unit vector. Measuring the pure state $[\varphi ]$ by the projective measurement onto the basis lines outputs $y\in Y$ with probability $p_{\varphi }(y)=\mathrm{\mid }⟨\varphi ,e_y⟩{\mathrm{\mid }}^2,{\sum }_{y\in Y}{p}_{\varphi }(y)=1.$ In particular, for self-adjoint $H:V\to V$, real $t$, and unit $\psi$, the walk output $\varphi =U_H(t)\psi$ is unit and $p_t(y)=\mathrm{\mid }⟨U_H(t)\psi ,e_y⟩{\mathrm{\mid }}^2$. For an initial vertex $e_x$, the probability of observing vertex $y$ is $\mathrm{\mid }⟨U_H(t)e_x,e_y⟩{\mathrm{\mid }}^2$.

Let $V$ be a nonzero finite-dimensional complex inner-product space with a finite orthonormal basis $(e_y{)}_{y\in Y}$. Let $\psi \in V$ be unit, let $U,W:V\to V$ be unitary, and let $\rho \ge 0$ satisfy $\mathrm{\parallel }W-U{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \rho$. If $p_U(y)$ and $p_W(y)$ are the computational-basis measurement probabilities after applying $U$ and $W$ to $\psi$, respectively, then for every $y\in Y$, $\mathrm{\mid }{p}_W(y)-p_U(y)\mathrm{\mid }\le 2\rho \mathrm{.}$

Let $V$ be a finite-dimensional complex register and let $H=H^{\ast }$ be its declared generator. The mathematical target at time $t\in \mathbb{R}$ is $U_H(t)$ from Finite Hermitian matrix dynamics. A Hamiltonian-access contract records how this target and its input data are supplied; it does not equate a matrix description with an implementation.

The contract declares one input representation:

1. Explicit terms: a finite ordered list of Hermitian matrices $H_1,\dots ,H_m$, real coefficients $c_1,\dots ,c_m$ with their exact or finite-precision binary encodings, and the identity $H={\sum }_{j=1}^m{c}_j{H}_j$. If the implementation calls the individual operations $U_{c_j{H}_j}(t_j)$, the contract lists every operation, its order, and its charge. The equality of their composition with $U_H(t)$ must be proved or supplied as a separate simulation certificate; it does not follow from the term list alone.
2. Row-sparse input: an integer sparsity bound $d$, a row-location oracle, and an entry-value oracle returning each selected matrix entry to a declared coefficient precision. Each oracle's full unitary action on invalid encodings, and every forward, inverse, or controlled call actually used, are explicit parts of the contract.

The contract separately names an implementation of the requested evolution:

• an ideal continuous-time operation $U_H(t)$ with its declared evolution time and/or evolution-query charge; or
• a finite unitary circuit/simulator $V_{H,t,ϵ}$ with a supplied certificate $\mathrm{\parallel }{V}_{H,t,ϵ}-U_H(t){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le ϵ$ and its gate, query, description-bit, coefficient-precision, and classical-construction costs.

Initial-state preparation and final measurement are separate supplied stages. For each stage the contract records a triple $(q,g,b)$: $q$ is the number of declared oracle or evolution calls, $g$ is the finite gate count in the chosen gate model, and $b$ is the declared input, operation-description, coefficient, and precision-bit charge. Circuit description length and gate count follow Circuit-family and computation cost model; they are distinct coordinates. Evolution time is reported separately unless the chosen model explicitly includes it in a query coordinate. Serial composition adds the declared stage coordinates. A controlled or inverse operation is charged only if the model explicitly grants that access or supplies a construction, as in Controlled Unitary Access and Inverse Unitary Access.

A complexity claim for a family of such inputs must also specify a uniform generator for the full circuit and access descriptions, as in Full-list uniform quantum circuit family, and state the costs as functions of the input size. The matrix alone supplies no efficient $U_H(t)$, controlled call, inverse call, or zero-cost operation. In particular, a Boolean marked-item oracle does not by itself grant the continuous-time operation $e^{-it\mathrm{\mid }{e}_w⟩⟨e_w\mathrm{\mid }}$; any conversion or simulation and its precision are separately specified and charged.

Input: An integer $n\ge 0$, an ordered $n$-qubit register initialized to $e_{0^n}$, and a Hamiltonian-access contract for $A_n:={\sum }_{j=0}^{n-1}{X}_j,$ where $X=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ and $X_j:=I_2^{\otimes j}\otimes X\otimes I_2^{\otimes (n-j-1)}$ is its tensor-map extension acting on factor $j$ and as the identity on every other factor, by Tensor products of finitely many linear maps. The contract must explicitly supply either the whole operation $U_{A_n}(\pi \mathrm{/}2)$ or the $n$ local operations $U_{X_j}(\pi \mathrm{/}2)$ in the declared ordered tensor factors. The local-operation option requests each one-qubit evolution separately; its equivalence to the whole evolution is proved by the correctness argument and is not assumed here. This contract does not make arbitrary matrix exponentiation free. Every supplied query, gate, description-bit, and synthesis cost is recorded under Continuous-time Hamiltonian access cost model and Circuit-family and computation cost model.

Procedure: If the whole operation is supplied, apply $U_{A_n}(\pi \mathrm{/}2)$ once. If the local operations are supplied, apply $U_{X_j}(\pi \mathrm{/}2)$ once for each $j=0,\dots ,n-1$ in increasing order. Then perform the computational-basis projective measurement and return the observed $n$-bit word. For $n=0$, the sum is empty, the register is the one-dimensional empty tensor product, the evolution is the identity, and the output word is empty. For every $n$, the operation and readout costs come from the declared access and circuit models; the matrix formula alone supplies no implementation or cost.

For every integer $n\ge 0$, the algorithm Hypercube continuous-time state transfer evolves the initial vector $e_{0^n}$ to $U_{A_n}(\pi \mathrm{/}2)e_{0^n}=(-i{)}^n{e}_{1^n}\mathrm{.}$ Consequently its computational-basis measurement outputs $1^n$ with probability one, including the empty word when $n=0$.

Inputs: An integer $N\ge 2$, an integer $m\ge \lceil {\log }_{2}N\rceil$, an injective label encoding $\mathsf{e}\mathsf{n}\mathsf{c}:[N]\to \{0,1{\}}^m$, and the corresponding $m$-qubit register. Its active subspace is $S:=\mathrm{span}\{e_{\mathsf{e}\mathsf{n}\mathsf{c}(x)}:x\in [N]\}$; bit strings outside the image of $\mathsf{e}\mathsf{n}\mathsf{c}$ are unused labels. The marked label $w\in [N]$ is available through the declared oracle/access model, not as an inspected classical value.

On $S$, define the complete-graph adjacency by $A{e}_{\mathsf{e}\mathsf{n}\mathsf{c}(x)}:={\sum }_{y\in [N],y\mathrm{\ne }x}{e}_{\mathsf{e}\mathsf{n}\mathsf{c}(y)},$ and extend $A$ by zero on $S^{\perp }$. Define $P_{w}z:=⟨z,e_{\mathsf{e}\mathsf{n}\mathsf{c}(w)}⟩e_{\mathsf{e}\mathsf{n}\mathsf{c}(w)}$ on the full register and the self-adjoint generator $H:=-A\mathrm{/}N-P_w$.

The input also supplies:

• a state-preparation circuit $A_s$ whose label-register output from the specified zero input is the pure state $e_s:=N^{-1\mathrm{/}2}{\sum }_{x\in [N]}{e}_{\mathsf{e}\mathsf{n}\mathsf{c}(x)}$; if its implementation uses workspace, the model states its initialization, final state, and separate query, gate, and description-bit costs;
• the total Boolean function $f_w:\{0,1{\}}^m\to \{0,1\}$ defined by $f_w(\mathsf{e}\mathsf{n}\mathsf{c}(x))=1$ exactly when $x=w$ and $f_w(z)=0$ on every unused label, together with the full unitary XOR-oracle access and its cost from Coherent XOR function oracle; and
• a Hamiltonian-access contract that supplies either the ideal $U_H(t)$ or a unitary simulator $V_{H,t,\rho }$ with a supplied certificate $\mathrm{\parallel }{V}_{H,t,\rho }-U_H(t){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \rho$, including all query, gate, description-bit, precision, and classical-construction costs.

The function oracle does not itself supply the continuous-time operation $U_H(t)$: any conversion from its marked predicate to evolution under $P_w$, and any simulation of the adjacency term, must be separately declared and charged under Continuous-time Hamiltonian access cost model.

Procedure: Prepare $e_s$, apply the supplied ideal evolution or simulator for $t=\pi \sqrt{N}\mathrm{/}2$, and measure the register in its computational basis using Finite projective measurements. Decode a measured string in the image of $\mathsf{e}\mathsf{n}\mathsf{c}$ to its label and return it; return FAIL on an unused string. If $N=2^n$ and $\mathsf{e}\mathsf{n}\mathsf{c}$ is the standard $n$-bit encoding, the supplied preparation may be $A_s=H^{\otimes n}$ by Hadamard preparation of a uniform binary state; charge $n$ gates when $H$ is primitive and the declared synthesis costs otherwise. For arbitrary $N$, $A_s$ is a supplied, charged input. No query, gate, or runtime bound follows from the finite matrix description alone.

For every integer $N\ge 2$, every marked label $w\in [N]$, and every encoded complete-graph search instance of Complete-graph continuous-time search whose supplied preparation produces $e_s=N^{-1\mathrm{/}2}{\sum }_x{e}_{\mathsf{e}\mathsf{n}\mathsf{c}(x)}$, exact evolution under $H=-A\mathrm{/}N-\mathrm{\mid }{e}_{\mathsf{e}\mathsf{n}\mathsf{c}(w)}⟩⟨e_{\mathsf{e}\mathsf{n}\mathsf{c}(w)}\mathrm{\mid }$ at $t=\pi \sqrt{N}\mathrm{/}2$ places the search register in the marked basis ray with probability exactly $1$. If that evolution is replaced by a unitary $V$ with $\mathrm{\parallel }V-U_H(t){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \rho$ for $\rho \ge 0$, the measured probability of the marked label is at least $1-2\rho$.