Szegedy walk unitaries for quantum maps

DOI10.1007/S00220-023-04797-4arXiv2107.07365OpenAlexW3182896201MaRDI QIDQ6135944FDOQ6135944

Authors: Pawel Wocjan, Kristan Temme 

Publication date: 28 August 2023

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Abstract: Szegedy developed a generic method for quantizing classical algorithms based on random walks [Proceedings of FOCS, 2004, pp. 32-41]. A major contribution of his work was the construction of a walk unitary for any reversible random walk. Such unitary posses two crucial properties: its eigenvector with eigenphase $0$ is a quantum sample of the limiting distribution of the random walk and its eigenphase gap is quadratically larger than the spectral gap of the random walk. It was an open question if it is possible to generalize Szegedy's quantization method for stochastic maps to quantum maps. We answer this in the affirmative by presenting an explicit construction of a Szegedy walk unitary for detailed balanced Lindbladians -- generators of quantum Markov semigroups -- and detailed balanced quantum channels. We prove that our Szegedy walk unitary has a purification of the fixed point of the Lindbladian as eigenvector with eigenphase $0$ and that its eigenphase gap is quadratically larger than the spectral gap of the Lindbladian. To construct the walk unitary we leverage a canonical form for detailed balanced Lindbladians showing that they are structurally related to Davies generators. We also explain how the quantization method for Lindbladians can be applied to quantum channels. We give an efficient quantum algorithm for quantizing Davies generators that describe many important open-system dynamics, for instance, the relaxation of a quantum system coupled to a bath. Our algorithm extends known techniques for simulating quantum systems on a quantum computer.

Full work available at URL: https://arxiv.org/abs/2107.07365

zbMATH Keywords

Lindbladians

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Estimates of eigenvalues in context of PDEs (35P15) Open systems, reduced dynamics, master equations, decoherence (81S22) General topics in the theory of algorithms (68W01) Canonical quantization (81S08) Mathematical modeling or simulation for problems pertaining to quantum theory (81-10) Quantum channels, fidelity (81P47)

Cites Work

• On the generators of quantum dynamical semigroups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hypercontractivity in noncommutative \(L_1\) spaces
• The $\chi ^2$χ2-divergence and mixing times of quantum Markov processes
• Quantum logarithmic Sobolev inequalities and rapid mixing
• On the detailed balance condition for non-Hamiltonian systems
• Quantum detailed balance and KMS condition
• Generators of dynamical semigroups
• Quantum Gibbs samplers: the commuting case
• Thermalization time bounds for Pauli stabilizer Hamiltonians
• Lower bounds to the spectral gap of Davies generators
• Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems
• Relating relative entropy, optimal transport and Fisher information: a quantum HWI inequality
• Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• On the modified logarithmic Sobolev inequality for the heat-bath dynamics for 1D systems
• Group Transference Techniques for the Estimation of the Decoherence Times and Capacities of Quantum Markov Semigroups
• Hypercontractivity and logarithmic Sobolev inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates
• Measuring 4-local qubit observables could probabilistically solve PSPACE

Cited In (2)

• Matrix-valued SzegoÌ polynomials and quantum random walks
• Equivalence of Szegedy's and coined quantum walks

This page was built for publication: Szegedy walk unitaries for quantum maps

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