106 citations · 126 across the 18 of their papers we have counts for
27 papers
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…
QMLP: An Error-Tolerant Nonlinear Quantum MLP Architecture using Parameterized Two-Qubit Gates
Cheng Chu, Nai-Hui Chia, Lei Jiang +1
Despite potential quantum supremacy, state-of-the-art quantum neural networks (QNNs) suffer from low inference accuracy. First, the current Noisy Intermediate-Scale Quantum (NISQ)…
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…
Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round
Nai-Hui Chia, Kai-Min Chung, Xiao Liang +1
From the minimal assumption of post-quantum semi-honest oblivious transfers, we build the first -simulatable two-party computation (2PC) against quantum polynomial-time (QPT) ad…
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…
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu +1
We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for . As a main result, we show that there is no constant-round post-qua…
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…
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Gilyén, Tongyang Li +3
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quant…
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…
Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming
Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin +1
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle subli…