Abstract: Density Matrix Exponentiation is a technique for simulating Hamiltonian dynamics when the Hamiltonian to be simulated is available as a quantum state. We present a natural analogue to this technique, called wave matrix Lindbladization, for simulating Markovian dynamics governed by the well known Lindblad master equation. In order to do so, we introduce an input model in which Lindblad operators are encoded into pure quantum states, called program states, and our technique simulates Lindbladian evolution by means of interacting the system of interest with these program states. We begin by focusing on a simple case in which the Lindbladian consists of only one Lindblad operator and a Hamiltonian. Thereafter, we extend the method to simulating general Lindbladians and other cases in which a Lindblad operator is expressed as a linear combination or a polynomial of the operators encoded into the program states. We propose quantum algorithms for all these cases and also investigate their sample complexities, i.e., the number of program states needed to simulate a given Lindbladian evolution approximately. Finally, we demonstrate that our quantum algorithms provide an efficient route for simulating Lindbladian evolution relative to the full tomography of encoded operators.

Abstract: Since Bell's historical observation that some nonlocal games can be won by quantum entangled players with higher probability than by classical players, the entangled two-prover model of computation has been a model of great interest in quantum complexity theory and quantum foundations. Recently, Kalai, Lombardi, Vaikuntanathan and Yang introduced a cryptographic compilation scheme which maps any nonlocal game to a single-prover cryptographically sound argument in a way that preserves quantum completeness and classical soundness, using quantum fully homomorphic encryption (or classical-client quantum blind delegation) in order to simulate the separation between the provers. We study the quantum soundness properties of this compilation scheme, and show how it can be used to prove results in classical-client quantum delegation in a modular and unified way by combining techniques that originate in the study of self-testing with cryptographic tools.