Yu-Ching Shen

collaborators

3 papers

quant-ph2026

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

Nai-Hui Chia, Atsuya Hasegawa, FranÃ§ois Le Gall +2

The local Hamiltonian (LH) problem is the canonical $QMA$ -complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that t…

quant-ph2025

Shadow Tomography Against Adversaries

Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia +4

We study single-copy shadow tomography in the adversarial robust setting, where the goal is to learn the expectation values of $M$ observables $O_{1}, \dots, O_{M}$ with $ε$ …

quant-ph2025

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O (2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH

Nai-Hui Chia, Yu-Ching Shen

We investigate the computational complexity of the Local Hamiltonian (LH) problem and the approximation of the Quantum Partition Function (QPF), two central problems in quantum man…

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

Shadow Tomography Against Adversaries

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: O(22n​) Algorithm Is Nearly Optimal under QSETH

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O (2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH