111 citations · 280 across the 15 of their papers we have counts for
12 papers · 1 filter
Efficient Quantum State Identity Testing
Shih-Han Hung, Ming-Hsien Tsai
We study the following quantum state identity problem: given access to copies of unknown pure quantum states, the goal is to determine whether every pair has fidelity at least…
No Size-Preserving Amplification with Quantum Advice
Shih-Han Hung, Han-Hsuan Lin
Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show…
Random Quantum Circuits Beyond Moment Matching
Shih-Han Hung
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which m…
Certified randomness amplification by dynamically probing remote random quantum states
Minzhao Liu, Pradeep Niroula, Matthew DeCross +49
Cryptography depends on truly unpredictable numbers, but physical sources emit biased or correlated bits. Quantum mechanics enables the amplification of imperfect randomness into n…
Certified randomness using a trapped-ion quantum processor
Minzhao Liu, Ruslan Shaydulin, Pradeep Niroula +29
While quantum computers have the potential to perform a wide range of practically important tasks beyond the capabilities of classical computers, realizing this potential remains a…
Certified Randomness from Quantum Supremacy
Scott Aaronson, Shih-Han Hung
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our pr…
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 query complexity with matrix-vector products
Andrew M. Childs, Shih-Han Hung, Tongyang Li
We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the tr…
Non-interactive classical verification of quantum computation
Gorjan Alagic, Andrew M. Childs, Alex B. Grilo +1
In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In t…
Quantum algorithm for estimating volumes of convex bodies
Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung +3
Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates…
Quantum algorithm for multivariate polynomial interpolation
Jianxin Chen, Andrew M. Childs, Shih-Han Hung
How many quantum queries are required to determine the coefficients of a degree- polynomial in variables? We present and analyze quantum algorithms for this multivariate pol…
Optimal quantum algorithm for polynomial interpolation
Andrew M. Childs, Wim van Dam, Shih-Han Hung +1
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Mey…