Time:
April 15th, 10:30-11:30am
Location:
HIMIS 7A1
Speaker:
Yu Wang
Title:
Quantum Advantage via Efficient Postprocessing on Qudit Classical Shadow Tomography
Abstract:
Many problems in quantum science can be formulated as estimating a trace quantity $tr(AB)$ for two high-dimensional matrices. Although the expression is simple, the cost of carrying it out classically can become enormous when the dimension grows exponentially. In this talk, I will introduce a new quantum approach based on classical shadow tomography that makes this task much more efficient for both qubit and qudit systems.
The main idea is to use a special family of randomized measurements, called dense dual bases (DDBs), which generate very sparse classical data. As a result, each measurement outcome can be postprocessed in constant time, leading to a significant reduction in overall computational cost. Compared with the usual quadratic dependence on dimension in direct classical computation, this approach yields near-linear worst-case scaling and polylogarithmic scaling in typical regimes. I will explain the basic construction, the intuition behind the efficiency gain, and several examples illustrating its use in expectation estimation, verification, and quantum information processing.
In the final part of the talk, I will also comment on some ongoing ideas for simplifying the depth of the underlying DDB circuits. This leads naturally to modular add-$r$ circuits, which form one of the basic arithmetic components in modular exponentiation and hence in Shor’s algorithm. From this perspective, depth reduction for DDB circuits may also connect to broader questions in efficient quantum circuit design.