Zoltan Zimboras

Markov Chain Monte Carlo (MCMC) methods are an essential tool in classical algorithms design. Especially, the Metropolis sampling algorithm and Glauber dynamics have drastically advanced our understanding of material properties, reaction dynamics, phase transitions, and thermodynamics. Recently, there has been a new wave of quantum MCMC algorithms that draws inspiration from the cooling process in Nature to design continuous-time Quantum Markov chains (i.e., Lindbladians) satisfying (approximate) detailed balance. Nevertheless, the quantum analog of detailed balance, which has been central to classical Markov chain design and analysis, has posed a challenge to quantum algorithms design and has only recently been achieved exactly and (quasi)-locally for an efficiently implementable Lindbladian by [CKG23]. The construction of [CKG23] provably leads to an efficient Gibbs state preparation method in the high-temperature regime. However, proving fast mixing for low temperatures remains an open problem, apart from some (almost) integrable systems. Here we introduce (i) a new continuous-time Lindbladian construction that also leads to quasi-local and detailed-balanced dynamics, and (ii) show that it is fast mixing for high-temperature lattice Hamiltonians. The new construction's major advantage is that it does not increase the number of Kraus operators, which is particularly helpful for numerical studies. We exploit the resulting low Kraus rank through a (iii) novel custom variant of density matrix renormalization group (DMRG) for superoperators to provide numerical evidence for various 1D models (Transverse-field Ising, Heisenberg XXZ) that the Gibbs sampler is mixing fast. We also introduce (iv) new detailed-balanced discrete-time quantum channel variants of all existing continuous-time detailed-balanced Lindbladian construction and (v) show that they are also mixing fast at high-temperatures, and provide some preliminary (vi) resource estimates for their implementation confirming their algorithmic efficiency.

In distributed computing, a Byzantine fault is a condition where a component behaves inconsistently, showing different symptoms to different components of the system. Consensus among the correct components can be reached by appropriately crafted communication protocols, even in the presence of byzantine faults. Quantum-aided protocols built upon distributed entangled quantum states are worth considering, as they are more resilient than traditional ones. Based on earlier ideas, here we introduce a parameter-dependent family of quantum-aided weak broadcast protocols, and prove their security. We analyze the resource requirements as functions of the protocol parameters, and locate the parameter range where these requirements are minimal. Hence, our work illustrates the engineering aspects of future deployments of such protocols in practice. Following earlier work demonstrating the suitability of noisy intermediate-scale quantum (NISQ) devices for the study of quantum networks, we show how to prepare our resource quantum state on publicly available IBM quantum computers. We outline follow-up tasks toward practical quantum-aided byzantine fault tolerance.