4.7 Orbit-quotient quantum walks
On this page · Permalink · Source line 1220
4.7.1 Orbit states
On this page · Permalink · Source line 1225
Let a group \(G\) act by automorphisms on a finite graph with vertex set \(V\). The orbits are \(\mathcal O_1,\ldots,\mathcal O_r\). Define normalized orbit states
If the adjacency or Hamiltonian \(H\) commutes with the group action, the span of these states is invariant whenever the partition is equitable.
The quotient matrix is
Theorem 4.9: Orbit-quotient collapse
Suppose a uniformly described quantum walk has a polynomial number \(r(n)\) of relevant orbits, an orbit-uniform initial state, an orbit-invariant final measurement, and polynomial-time algorithms for orbit sizes, quotient entries, initial orbit coordinates, and the restricted final measurement. For continuous-time evolution, also assume a polynomial bound on \(|t|\|\widetilde H\|\) and efficient entry access to the precision required by the simulation. Then the walk can be simulated classically in polynomial time by the \(r(n)\times r(n)\) quotient dynamics.
Proof
The orbit-state span is invariant. The state is represented by \(r(n)\) amplitudes. Polynomial-time computation of quotient entries and ordinary polynomial-precision linear algebra satisfy Theorem 3.7.
4.7.2 Hypercube example
On this page · Permalink · Source line 1251
The \(n\)-dimensional hypercube is invariant under coordinate permutations. Its vertex orbits are Hamming-weight layers \(0,1,\ldots,n\). In the normalized orbit basis, the quotient adjacency has couplings
Thus a walk on \(2^n\) vertices initialized at \(0^n\) evolves in an \((n+1)\)-dimensional subspace.
4.7.3 The succinct-input caveat
On this page · Permalink · Source line 1267
If the full graph is supplied explicitly, a polynomial-in-\(|V|\) algorithm may still be exponential in the succinct parameter \(n\). The theorem requires quotient data computable directly from the succinct graph description. Discovering graph automorphisms or orbit partitions can itself be difficult. For regular families such as hypercubes, Johnson graphs, association schemes, and Cayley graphs with known character theory, the quotient is explicit.
4.7.4 Fourier packets
On this page · Permalink · Source line 1270
On a cycle, translation characters diagonalize the adjacency operator. The continuous-time walk
is a sum of Fourier-character packets. This is the same discrete Fourier transform that appears as a signal-processing coordinate change, a group-character decomposition, and a quantum basis transformation.