Quantum Stochastic Processes with Kirkwood-Dirac Quasiprobabilities

Classical stochastic processes — multi-time joint probability distributions over outcomes — are powerful and ubiquitous tools for modelling owing to their ability to capture full statistics and temporal correlations. In this work, we look into an alternative description of a quantum stochastic process obtained from a multi-time quantum process with measurements at each discrete time using Kirkwood-Dirac (KD) quasiprobability, which we refer to as the KD-process.  We show that the KD-process can well characterize whether a stochastic process is classical/quantum and Markovian/non-Markovian.  In particular, we demonstrate consistency with the classification of non-coherence-detecting-and-generating (NCGD) and non-discord-generating-and-detecting (NDGD) dynamics as classical processes. Moreover, we show through several examples that the KD-process recovers the underlying classical stochastic process, whereas the standard approach characterized as quantum -- thus drawing a tighter bound at the classical-quantum boundary. We discuss the classical simulability of the KD-process using a Monte Carlo sampling method, and identify  space complexity and  sampling complexity as the additional resources for the simulation. We find that sampling complexity grows with the nonpositivity of the KD-process, and that Markov processes enable Markov chain sampling, which can significantly reduce the space complexity. Lastly, we demonstrate an application of the KD-process as a tool to examine the probabilistic evolutions of quantum computing. Using Grover's algorithm as a case study, the KD-process reveals a Markovian structure with striking resemblance to the classical unstructured search algorithm, and that sampling complexity grows sub-exponentially with the search size — signifying the hardness of classically simulating quantum computation even when the computational speedup is only  quadratic.