MIXING OF QUANTUM WALKS ON GENERALIZED HYPERCUBES

摘要: We study continuous-time quantum walks on graphs which generalize the hypercube. The only known family of whose walk instantaneously mixes to uniform is Hamming with small arities. show that mixing hypercube robust under addition perfect matchings but not much else. Our specific results include: • graph obtained by augmenting an additive matching x ↦ ⊕ η instantaneous whenever |η| even, a slower time. This strictly includes result Moore and Russell1 class H(n,q) if q ≥ 5. tight characterization graphs; previously, status < 5 was known. bunkbed adjacency matrix I ⊗ Qn + X Af, where Af -circulant defined Boolean function f, Fourier transform f has support size smaller than 2n-1. explains why join two hypercubes not. work exploits rich spectral structure generalized relies heavily analysis group-circulants.