Szegedy Walk Unitaries for Quantum Maps

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.

References in corpus (16)

• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A Grand Unification of Quantum Algorithms
• Quantum Metropolis Sampling
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Quantum Simulations of Classical Annealing Processes
• A Quantum-Quantum Metropolis Algorithm
• Quantum logarithmic Sobolev inequalities and rapid mixing
• The ${\chi }^2$-divergence and Mixing times of quantum Markov processes
• Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems
• Lower bounds to the spectral gap of Davies generators
• On the modified logarithmic Sobolev inequality for the heat-bath dynamics for 1D systems
• The modified logarithmic Sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions
• Estimating the decoherence time using non-commutative Functional Inequalities
• Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• Measuring 4-local n-qubit observables could probabilistically solve PSPACE

Cited by in corpus (12)

• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Thermal State Preparation via Rounding Promises
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Quantum computational advantage with constant-temperature Gibbs sampling
• Mixing Time of Open Quantum Systems via Hypocoercivity
• The topology of data hides in quantum thermal states
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Lindblad engineering for quantum Gibbs state preparation under the eigenstate thermalization hypothesis
• Area law for steady states of detailed-balance local Lindbladians
• Quantized Markov Chain Couplings that Prepare Qsamples
• Efficient and simple Gibbs state preparation of the 2D toric code via duality to classical Ising chains