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.

We study the formation of short-depth designs beyond the unitary group. We provide a range of results on several groups of broad interest in quantum information science: the Clifford group, the orthogonal group, the unitary symplectic groups, and the matchgate group. For all of these groups, we prove that analogues of unitary designs cannot be generated by any circuit ensemble with light-cones that are smaller than the system size. This implies linear lower bounds on the circuit depth in one-dimensional systems. For the Clifford, orthogonal, and unitary symplectic group, we moreover show that commonly considered circuit ensembles cannot generate designs in sub-linear depth on any circuit architecture. We show this by exploiting observables in the higher-order commutants of each group, which allow one to distinguish any short-depth circuit from truly random. While these no-go results rule out short-depth designs over these subgroups, we prove that slightly weaker forms of randomness---including additive-error state designs and anti-concentration in sampling distributions---nevertheless emerge at logarithmic depths in many cases. Our results reveal that the onset of randomness in shallow quantum circuits is a widespread yet subtle phenomenon, dependent on the interplay between the group itself and the context of its application.

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.