4 papers
Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties
Zhong-Xia Shang, Dong An, Changpeng Shao
Fast-forwarding refers to the ability to simulate a system of time using significantly fewer than queries or circuit depth. While various Hamiltonian systems are known to c…
DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
Zhengfeng Ji, Tongyang Li, Changpeng Shao +2
We study the computational complexity of estimating the normalized trace for a log-local Hamiltonian acting on qubits. This problem arises naturally in the…
Quantum and classical query complexities of functions of matrices
Ashley Montanaro, Changpeng Shao
Let be an -sparse Hermitian matrix, be a univariate function, and be two indices. In this work, we investigate the query complexity of approximating $\bra{i} f…
Low-degree approximation of QAC circuits
Ashley Montanaro, Changpeng Shao, Dominic Verdon
QAC is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show t…