Weak Simulation

Stefan Hillmich, Robert Wille

Dongsheng Wang

In this work, we introduce different types of quantum simulations according to different operator topologies on a Hilbert space, namely, uniform, strong, and weak quantum simulations. We show that they have the same computational power that the efficiently solvable problems are in bounded-error quantum polynomial time. For the weak simulation, we formalize a general weak quantum simulation problem and construct an algorithm which is valid for all instances. Also, we analyze the computational power of quantum simulations by proving the query lower bound for simulating a general quantum process.

Stefan Hillmich, Robert Wille

Sören Kreinberg, Piotr Novik, Igor Koltchanov +1 more

We demonstrate how an existing simulation framework for modelling classical optical systems can be utilized for simulations of weak-coherent QKD links.

Lucas Kocia

Bounding the cost of classically simulating the outcomes of universal quantum circuits to additive error $δ$ is often called weak simulation and is a direct way to determine when they confer a quantum advantage. Weak simulation of the $T$+Clifford gateset is $BQP$-complete and is expected to scale exponentially with the number $t$ of $T$ gates. We constructively tighten the upper bound on the worst-case $L_1$ norm sampling cost to next order in $t$ from $\mathcal O(ξ^t δ^{-2})$ if $δ^2 \gg ξ^{-t}$ to $\mathcal O((ξ^t{-}t) δ^{-2} )$ if $δ^2 \gg (ξ^t -t)^{-1}$, where $ξ^t = 2^{\sim 0.228 t}$ is the stabilizer extent of the $t$-tensored $T$ gate magic state. We accomplish this by replacing independent $L_1$ sampling in the popular SPARSIFY algorithm used in many weak simulators with correlated $L_1$ sampling. As an aside, this result demonstrates that the $T$ gate magic state's approximate stabilizer state decomposition is not multiplicative with respect to $t$, for finite values, despite the multiplicativity of its stabilizer extent. This is the first weak simulation algorithm that has lowered this bound's dependence on finite $t$ in the worst-case to our knowledge and establishes how to obtain further such reductions in $t$.

Scott Kirkpatrick