• 综合性科技类中文核心期刊
    • 中国科技论文统计源期刊
    • 中国科学引文数据库来源期刊
    • 中国学术期刊文摘数据库（核心版）来源期刊
    • 中国学术期刊综合评价数据库来源期刊
Advance Search
JIANG Nan, WANG Zichen, WANG Jian, WANG Hailiang. Optimization of Quantum Symbolic Execution[J]. Journal of Beijing University of Technology, 2023, 49(6): 621-629. DOI: 10.11936/bjutxb2022090045
Citation: JIANG Nan, WANG Zichen, WANG Jian, WANG Hailiang. Optimization of Quantum Symbolic Execution[J]. Journal of Beijing University of Technology, 2023, 49(6): 621-629. DOI: 10.11936/bjutxb2022090045
shu

Optimization of Quantum Symbolic Execution

  • 1.

    Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China

  • 2.

    Beijing Key Laboratory of Trusted Computing, Beijing 100124, China

  • 3.

    Beijing Key Laboratory of Security and Privacy in Intelligent Transportation, Beijing Jiaotong University, Beijing 100044, China

More Information
  • Received Date: September 28, 2022
  • Revised Date: December 16, 2022
  • Available Online: June 08, 2023
    Graphical Abstract
    • Abstract

  • Quantum symbolic execution is a technique for generating test cases for quantum programs. At present, quantum symbol execution only mechanically divides the test case space continuously according to each conditional statement in the debugged program, without considering the entire expression and the nesting of conditional statements, which results in complex quantum circuits. To solve this problem, this paper proposed an optimization of quantum symbols. First, by simplifying the relational expression, the number of quantum modules was directly reduced, or the number of quantum modules was indirectly reduced through the substitution of values. Second, the methods of simplifying circuit for logic AND and logic OR were presented, respectively. Finally, it was proposed that the nested conditional statement was regarded as the logic AND of outer layer and inner layer to simplify the circuit, and optimize the division of the test case space in the quantum symbolic execution. Results show that this optimization method reduces the cost of implementing quantum symbolic execution circuits, including the number of quantum gates and qubits.

    • FullText(HTML)
    • References (27)
  • [1]
    NIELSEN M A, CHUANG I, GROVER L K. Quantum computation and quantum information[J]. American Journal of Physics, 2002, 70(5): 558-559. http://avierfjard.com/PDFs/Quantum/Tutorials/Quantum%20Information%20Processing/Lecture_0.pdf
    [2]
    JIANG N Q, LIANG X, WANG M F. Programmable quantum processor implemented with superconducting circuit[J]. Communications in Theoretical Physics, 2021, 73(5): 055102. doi: 10.1088/1572-9494/abe4cb
    [3]
    ZHONG H S, WANG H, DENG Y H, et al. Quantum computational advantage using photons[J]. Science, 2020, 370(6523): 1460-1463. doi: 10.1126/science.abe8770
    [4]
    ARUTE F, ARYA K, BABBUSH R, et al. Quantum supremacy using a programmable superconducting processor[J]. Nature, 2019, 574(7779): 505-510. doi: 10.1038/s41586-019-1666-5
    [5]
    BROUGHTON M, VERDON G, MCCOURT T, et al. Tensorflow quantum: a software framework for quantum machine learning[J]. ArXiv Preprint arXiv, 2020: 2003. 02989.
    [6]
    CROSS A. The ibm q experience and qiskit open-source quantum computing software[C]//APS March Meeting Abstracts. Maryland: American Physical Society, 2018, 2018: L58. 003.
    [7]
    PAOLINI L, PICCOLO M, ZORZI M. Qpcf: higher-order languages and quantum circuits[J]. Journal of Automated Reasoning, 2019, 63(4): 941-966. doi: 10.1007/s10817-019-09518-y
    [8]
    SELINGER P. Towards a quantum programming language[J]. Mathematical Structures in Computer Science, 2004, 14(4): 527-586. doi: 10.1017/S0960129504004256
    [9]
    ADEDOYIN A, AMBROSIANO J, ANISIMOV P, et al. Quantum algorithm implementations for beginners[J]. ArXiv Preprint arXiv, 2018: 1804. 03719.
    [10]
    HE C, LI J, LIU W. An exact quantum principal component analysis algorithm based on quantum singular value threshold[J]. ArXiv Preprint arXiv, 2020: 2010. 00831.
    [11]
    O'BRIEN T E, TARASINSKI B, TERHAL B M. Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments[J]. New Journal of Physics, 2019, 21(2): 023022. doi: 10.1088/1367-2630/aafb8e
    [12]
    PALTENGHI M, PRADEL M. Bugs in quantum computing platforms: an empirical study[J]. Proceedings of the ACM on Programming Languages, 2022, 6(OOPSLA1): 1-27. http://www.xueshufan.com/publication/3208388786
    [13]
    WANG J, GAO M, JIANG Y, et al. Quanfuzz: fuzz testing of quantum program[J]. ArXiv Preprint arXiv, 2018: 1810. 10310.
    [14]
    MIRANSKYY A, ZHANG L, DOLISKANI J. Is your quantum program bug-free?[J]. ArXiv Preprint arXiv, 2020: 2001. 10870.
    [15]
    ZHAO P, ZHAO J, MA L. Identifying bug patterns in quantum programs[C]//2021 IEEE/ACM 2nd International Workshop on Quantum Software Engineering. Piscataway: IEEE, 2021: 16-21.
    [16]
    HUANG Y, MARTONOSI M. Statistical assertions for validating patterns and finding bugs in quantum programs[C]// Proceedings of the 46th International Symposium on Computer Architecture. New York: Association for Computing Machinery, 2019: 541-553.
    [17]
    JAVADIABHARI A, PATIL S, KUDROW D, et al. Scaffcc: scalable compilation and analysis of quantum programs[J]. Parallel Computing, 2015, 45: 2-17. doi: 10.1016/j.parco.2014.12.001
    [18]
    BRIGHT P. Microsoft's Q# quantum programming language out now in preview[EB/OL]. Ars Technica, (2017-12-05)[2022-09-06]. https://cacm.acm.org/careers/223549-microsofts-q-quantum-programming-language-out-now-in-preview/fulltext.
    [19]
    LIU J, BYRD G T, ZHOU H. Quantum circuits for dynamic runtime assertions in quantum computation[C]//Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. New York: Association for Computing Machinery, 2020: 1017-1030.
    [20]
    LI G, ZHOU L, YU N, et al. Proq: projection-based runtime assertions for debugging on a quantum computer[J]. ArXiv Preprint arXiv, 2019: 1911. 12855.
    [21]
    LIU J, ZHOU H. Systematic approaches for precise and approximate quantum state runtime assertion[C]//2021 IEEE International Symposium on High-Performance Computer Architecture. Piscataway: IEEE, 2021: 179-193.
    [22]
    ALI S, ARCAINI P, WANG X, et al. Assessing the effectiveness of input and output coverage criteria for testing quantum programs[C]//2021 14th IEEE Conference on Software Testing, Verification and Validation. Piscataway: IEEE, 2021: 13-23.
    [23]
    KING J C. Symbolic execution and program testing[J]. Communications of the ACM, 1976, 19(7): 385-394. doi: 10.1145/360248.360252
    [24]
    CADAR C, SEN K. Symbolic execution for software testing: three decades later[J]. Communications of the ACM, 2013, 56(2): 82-90. doi: 10.1145/2408776.2408795
    [25]
    JIANG N, WANG Z C, WANG J. Quantum symbolic execution[J]. ArXiv Preprint arXiv, 2022: 2209. 08582.
    [26]
    DINGES P, AGHA G. Solving complex path conditions through heuristic search on induced polytopes[C]// Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York: Association for Computing Machinery, 2014: 425-436.
    [27]
    LI Z, ZOU D, XU S, et al. Vuldeepecker: a deep learning-based system for vulnerability detection[J]. ArXiv Preprint arXiv, 2018: 1801, 01681.
    • Related Articles

  • Related Articles

    [1]FENG Shiquan, HU Yihuai. Construction and Simplification of the Combustion Mechanism of Gasoline Engine With Steam Reforming With the Heat of Exhaust Gas[J]. Journal of Beijing University of Technology, 2016, 42(12): 1901-1906. DOI: 10.11936/bjutxb2016030018
    [2]HOU Shi-wei, LU De-chun, DU Xiu-li. Production Conditions and Formation Mechanism of Shear Band Under Plane Strain Condition[J]. Journal of Beijing University of Technology, 2012, 38(7): 1025-1031. DOI: 10.3969/j.issn.0254-0037.2012.07.012
    [3]DU Xiao-hui, YIN Bao-cai, KONG De-hui. Edge Collapse Simplification Based on Weighted Quadric Error Metrics[J]. Journal of Beijing University of Technology, 2007, 33(7): 731-736. DOI: 10.3969/j.issn.0254-0037.2007.07.012
    [4]CHEN Nai-hui. Constructive Representation for Conditional Mathematical Expectation[J]. Journal of Beijing University of Technology, 2006, 32(6): 558-562. DOI: 10.3969/j.issn.0254-0037.2006.06.018
    [5]CHEN Zhi-tai, YU Yue-qing, DU Zhao-cai. A Simplification Method for Determinating Degree-of-freedom of Compliant Mechanisms[J]. Journal of Beijing University of Technology, 2005, 31(3): 225-228. DOI: 10.3969/j.issn.0254-0037.2005.03.001
    [6]He Chungeng, Chen Dapei, Ma Yilin, Wang Yu. The Conditions for Equivalence of Networks[J]. Journal of Beijing University of Technology, 1992, 18(4): 92-99.
    [7]Meng Dazhi. Conditions to Separatable Gerachgorin Plates[J]. Journal of Beijing University of Technology, 1992, 18(3): 28-32,40.
    [8]Lu Tingquan. The Sufficient and Necessary Condition of Two Similar Points in a Graph[J]. Journal of Beijing University of Technology, 1989, 15(4): 63-66.
    [9]Deng Naiyang. Nested Dissection Methods and their Application[J]. Journal of Beijing University of Technology, 1989, 15(1): 1-9. DOI: 10.3969/j.issn.0254-0037.1989.01.001
    [10]Zheng Bing, Xu Ning-shou. Simplification of High Order Linear Systems Using Block-pulse Functions[J]. Journal of Beijing University of Technology, 1983, 9(2): 71-78.

Catalog

    Get Citation
    PDF
    XML
    Article views (593) PDF downloads (43) Cited by()
    Turn off MathJax
    Article Contents
    Abstract
    References
    Related Articles

    Copyright © Editorial Department of Journal of Beijing University of Technology京公安备11019343018-20001

    Address：No.100 Pingleyuan, Chaoyang District, Beijing 100124,ChinaE-mail：xuebao_bjut@vip.163.com

    Supported by: Beijing Renhe Information Technology Co., Ltd.  Baidu Analytics

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return