106 citations · 126 across the 18 of their papers we have counts for
21 papers · 1 filter
Shadow Quantum Singular Value Transformation with Shallow Quantum Circuits
Nai-Hui Chia, Hyunseong Kim, Chia-Ying Lin +1
We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state , a Hermitian matrix , a polynomial , and a set of observables $\{O…
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +1
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 …
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…
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…
Adversarially robust quantum state learning and testing
Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia +1
Quantum state learning is a fundamental problem in physics and computer science. As near-term quantum devices are error-prone, it is important to design error-resistant algorithms.…
Complexity Theory for Quantum Promise Problems
Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang +2
We begin by establishing structural results for several fundamental quantum complexity classes: p/mBQP, p/mQ(C)MA, , p/mQIP, p/mBQP/qpoly, p/mBQP/poly,…
The Black-Box Simulation Barrier Persists in a Fully Quantum World
Nai-Hui Chia, Kai-Min Chung, Xiao Liang +1
Zero-Knowledge (ZK) protocols have been intensely studied due to their fundamental importance and versatility. However, quantum information's inherent differences significantly alt…
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…
Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
Nai-Hui Chia, Min-Hsiu Hsieh, Shih-Han Hung +1
This work investigates the oracle separation between the physically motivated complexity class of noisy quantum circuits, inspired by definitions such as those presented by Chen, C…
Quantum State Learning Implies Circuit Lower Bounds
Nai-Hui Chia, Daniel Liang, Fang Song
We establish connections between state tomography, pseudorandomness, quantum state synthesis, and circuit lower bounds. In particular, let be a family of non-uniform…
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…
On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation
Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh +3
Hamiltonian simulation is one of the most important problems in the field of quantum computing. There have been extended efforts on designing algorithms for faster simulation, and…
Classical verification of quantum depth
Nai-Hui Chia, Shih-Han Hung
We present two protocols for classical verification of quantum depth. Our protocols allow a purely classical verifier to distinguish devices with different quantum circuit depths e…
Quantum Meets the Minimum Circuit Size Problem
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang +1
In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It…
A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, th…
Classical Verification of Quantum Computations with Efficient Verifier
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
In this paper, we extend the protocol of classical verification of quantum computations (CVQC) recently proposed by Mahadev to make the verification efficient. Our result is obtain…
On the Quantum Complexity of Closest Pair and Related Problems
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin +2
The closest pair problem is a fundamental problem of computational geometry: given a set of points in a -dimensional space, find a pair with the smallest distance. A classic…
On the Need for Large Quantum Depth
Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai
Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates, and thus a potential way to use these quantum devices is using a hybrid sch…
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions
Nai-Hui Chia, Sean Hallgren, Fang Song
A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to av…
How hard is deciding trivial versus nontrivial in the dihedral coset problem?
Nai-Hui Chia, Sean Hallgren
We study the hardness of the dihedral hidden subgroup problem. It is known that lattice problems reduce to it, and that it reduces to random subset sum with density and also…