We present sqire, a low-level language for quantum computing and verification. sqire uses a global register of quantum bits, allowing easy compilation to and from existing `quantum assembly' languages and simplifying the verification process. We demonstrate the power of sqire as an intermediate representation of quantum programs by verifying a number of useful optimizations, and we demonstrate sqire's use as a tool for general verification by proving several quantum programs correct.

UR - https://arxiv.org/abs/1904.06319 ER - TY - JOUR T1 - Quantitative Robustness Analysis of Quantum Programs (Extended Version) JF - Proc. ACM Program. Lang. Y1 - 2018 A1 - Shih-Han Hung A1 - Kesha Hietala A1 - Shaopeng Zhu A1 - Mingsheng Ying A1 - Michael Hicks A1 - Xiaodi Wu AB -Quantum computation is a topic of significant recent interest, with practical advances coming from both research and industry. A major challenge in quantum programming is dealing with errors (quantum noise) during execution. Because quantum resources (e.g., qubits) are scarce, classical error correction techniques applied at the level of the architecture are currently cost-prohibitive. But while this reality means that quantum programs are almost certain to have errors, there as yet exists no principled means to reason about erroneous behavior. This paper attempts to fill this gap by developing a semantics for erroneous quantum while-programs, as well as a logic for reasoning about them. This logic permits proving a property we have identified, called ε-robustness, which characterizes possible "distance" between an ideal program and an erroneous one. We have proved the logic sound, and showed its utility on several case studies, notably: (1) analyzing the robustness of noisy versions of the quantum Bernoulli factory (QBF) and quantum walk (QW); (2) demonstrating the (in)effectiveness of different error correction schemes on single-qubit errors; and (3) analyzing the robustness of a fault-tolerant version of QBF.

VL - 3 U4 - Article 31 UR - https://arxiv.org/abs/1811.03585 CP - POPL U5 - https://doi.org/10.1145/3290344 ER - TY - JOUR T1 - Quantum algorithm for multivariate polynomial interpolation JF - Proceedings of The Royal Society A Y1 - 2018 A1 - Jianxin Chen A1 - Andrew M. Childs A1 - Shih-Han Hung AB -How many quantum queries are required to determine the coefficients of a degree-d polynomial in n variables? We present and analyze quantum algorithms for this multivariate polynomial interpolation problem over the fields Fq, R, and C. We show that kC and 2kC queries suffice to achieve probability 1 for C and R, respectively, where kC = ⌈ 1 n+1 ( n+d d )⌉ except for d = 2 and four other special cases. For Fq, we show that ⌈ d n+d ( n+d d )⌉ queries suffice to achieve probability approaching 1 for large field order q. The classical query complexity of this problem is ( n+d d ), so our result provides a speedup by a factor of n + 1, n+1 2 , and n+d d for C, R, and Fq, respectively. Thus we find a much larger gap between classical and quantum algorithms than the univariate case, where the speedup is by a factor of 2. For the case of Fq, we conjecture that 2kC queries also suffice to achieve probability approaching 1 for large field order q, although we leave this as an open problem.

VL - 474 UR - http://rspa.royalsocietypublishing.org/content/474/2209/20170480 CP - 2209 U5 - 10.1098/rspa.2017.0480 ER - TY - JOUR T1 - Optimal quantum algorithm for polynomial interpolation JF - 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) Y1 - 2016 A1 - Andrew M. Childs A1 - Wim van Dam A1 - Shih-Han Hung A1 - Igor E. Shparlinski AB -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 Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability.

VL - 55 U4 - 16:1--16:13 SN - 978-3-95977-013-2 UR - http://arxiv.org/abs/1509.09271 U5 - http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.16 ER -