10 papers
Efficient Matrix Product State Learning in Logarithmic Depth
Chia-Ying Lin, Nai-Hui Chia, Shih-Han Hung
Learning the closest matrix product state (MPS) representation of a quantum state enables useful tools for quantum machine learning and analysis of complex quantum systems. In this…
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 -complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that t…
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 observables with …
A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm
Junhyung Lyle Kim, Nai-Hui Chia, Anastasios Kyrillidis
Solving systems of linear equations is a fundamental problem, but it can be computationally intensive for classical algorithms in high dimensions. Existing quantum algorithms can a…
A Cryptographic Perspective on the Verifiability of Quantum Advantage
Nai-Hui Chia, Honghao Fu, Fang Song +1
In recent years, achieving verifiable quantum advantage on a NISQ device has emerged as an important open problem in quantum information. The sampling-based quantum advantages are…
3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: 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…