Approximate locality for quantum systems on graphs

DOI10.1103/PHYSREVLETT.101.140503MaRDI QIDQ3107627zbMATH OpenOpenAlexWikidataFDO

Authors Tobias J. Osborne

Publication date 26 December 2011

Published in Physical Review Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0611231

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Selfadjoint operator theory in quantum theory, including spectral analysis (81Q10)

Abstract: In this Letter we make progress on a longstanding open problem of Aaronson and Ambainis [Theory of Computing 1, 47 (2005)]: we show that if A is the adjacency matrix of a sufficiently sparse low-dimensional graph then the unitary operator e^{itA} can be approximated by a unitary operator U(t) whose sparsity pattern is exactly that of a low-dimensional graph which gets more dense as |t| increases. Secondly, we show that if U is a sparse unitary operator with a gap Delta in its spectrum, then there exists an approximate logarithm H of U which is also sparse. The sparsity pattern of H gets more dense as 1/Delta increases. These two results can be interpreted as a way to convert between local continuous-time and local discrete-time processes. As an example we show that the discrete-time coined quantum walk can be realised as an approximately local continuous-time quantum walk. Finally, we use our construction to provide a definition for a fractional quantum fourier transform.

Recommendations

• On the relationship between continuous- and discrete-time quantum walk
• Local subgraph structure can cause localization in continuous-time quantum walk
• Efficient circuits for quantum walks
• Exact simulation of coined quantum walks with the continuous-time model
• QUANTUM WALKS ON GENERAL GRAPHS

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• A remark on the cluster theorem
• Functional Analysis
• Quantum search of spatial regions

Cited in

(6)

• Almost commuting unitaries with spectral gap are near commuting unitaries
• Graphs of unitary matrices and positive semidefinite zero forcing
• Unitarity plus causality implies localizability
• Localization on quantum graphs with random edge lengths
• Locality for quantum systems on graphs depends on the number field
• Impact of global and local interaction on quantum spatial search on chimera graph

This page was built for publication: Approximate locality for quantum systems on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3107627)