Exponential quantum-classical query separations for cyclic ForrelationResearch Paper
A quantum computation can encode information in the trace of a product of matrices. Understanding the classical cost of estimating that trace helps distinguish the resources supplied by quantum access from those supplied by ordinary oracle queries. The one-clean-qubit model, also called DQC1, studies computations with one initially pure qubit and an…