Quantum Computing

 Publications:

• July 2026, Accepted to FOCS 2026 - Quantum channel tomography: optimal bounds and a

Heisenberg-to-classical phase transition 

with Kean Chen, Filippo Girardi, Aadil Oufkir, Zhicheng Zhang.    

This paper studies quantum channel tomography sample complexity, identifying the dilation rate as the key parameter governing Heisenberg versus classical scaling.

• April 2026. Accepted to ICDCS 2026 - Rethinking Quantum Network Design using a Verification-Based Quantum Transmission Protocol

With Yiming Zeng, Zhengyu Wu, Yuanyuan Yang and Aruna Balasubramanian

Congratulations Du!

This paper has won the Distinguished Paper Award of IEEE ICDCS 2026 in June! 

• April 2026. Accepted to CAV 2026 - How Many Circuit Identities Are Needed to Generate All Others?

With Yuantian Ding and Xiaokang Qiu

We provide strong evidence that a small set of independent identities suffices to generate all bounded-depth circuit equivalences. For Clifford+T circuits up to 9 qubits and depth 10, fewer than 20 identities suffice; for up to 5 qubits and depth 10, just 17 identities—each involving at most 3 qubits—are sufficient.

• April 2026. Accepted to PLDI 2026 - SAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum Circuits

[2507.13635] SAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum Circuits 

With Jens Palsberg and Thomas Reps

We present a logic for reasoning in such settings, called SAQR-QC. The logic supports {S}calable but {A}pproximate {Q}uantitative {R}easoning about {Q}uantum {C}ircuits.

• January 2026. Accepted to STOC 2026 - Approximation does not help in unitary time-reversal

[2507.05736] Approximation does not help in quantum unitary time-reversal 

With Kean Chen and Zhicheng Zhang

We show that approximation does not reduce the query complexity of quantum unitary time-reversal: any implementation of $U^{-1}$ up to error $\epsilon$ requires at least $(1-\epsilon)d^2$ queries to $U$.

• November 2025. Accepted to QIP 2026 - Pauli tomography at your fingertips.

[2507.22001] Pauli Measurements Are Near-Optimal for Single-Qubit Tomography  

With Jayadev Acharya, Abhilash Dharmavarapu, and Yuhan Liu. 

We show that $10^n$ samples are both necessary and sufficient for $n$-qubit state tomography, up to a $\sqrt{n}$ factor.

• August 2025. Accepted to QUANTUM journal - Adaptivity is not helpful for Pauli channel learning

arxiv.org/abs/2403.09033. Congratulations Du!

We prove that adaptivity does not offer any additional advantage (compared to non-adaptive strategies) in learning and testing Pauli channel if entangled resources are available.

• August 2025. Accepted to OOPSLA25: Scalable Equivalence Checking and Verification of Shallow Quantum Circuits 

arXiv:2504.01558 

With Thomas Reps.  

Congratulations Du!

This paper address the problem of checking if two shallow (i.e., constant-depth) quantum circuits are equivalent using efficient their classical description.

• Accepted to IEEE Transactions on Information Theory - Optimal Tomography of Quantum Markov Chains via Continuity of Petz Recovery States

arXiv:2209.02240

• Published in STOC 2025 — Pauli Measurements Are Not Optimal for Single-Copy Tomography

arXiv:2502.18170, DOI  With Jayadev Acharya, Abhilash Dharmavarapu, and Yuhan Liu. 

We show that Pauli measurements, while popular in practice, are not optimal for single-copy quantum state tomography, and we characterize the gap between Pauli and optimal measurements.

• Accepted to IEEE Transactions on Information Theory (TIT) — Quantum Max-Flow Min-Cut Theorem

arXiv:2110.00905 

This paper establishes a quantum analog of the classical max-flow min-cut theorem, with implications for quantum network theory and communication complexity.

• Published in Information and Computation — Quantum Temporal Logic and Reachability Problems of Matrix Semigroups

Science Direct We develop a temporal logic framework for reasoning about quantum systems and analyze the complexity of reachability problems in matrix semigroups.