Quantum software stacks (QSSs), which provide quantum circuit transformers and simulators, enable circuit transformations and the execution of circuits on classical computers. Despite their importance, they have not been effectively tested yet, leaving the correctness in question. The main obstacle to testing is the absence of a testing oracle, which checks the semantics-preservation of circuit transformations and the correctness of simulation results. While previous studies have employed differential and metamorphic testing to circumvent the necessity for an oracle, they have detected very few non-crash bugs. In this work, we address this gap by introducing QASMInfer, an exact inference system for quantum circuits, which computes the probability distribution of possible circuit outcomes. By supporting circuits written in OpenQASM, the de facto standard quantum assembly language used by most QSSs, QASMInfer acts as a unified testing oracle for multiple QSSs. Our design of QASMInfer achieves three key goals: (1) support for dynamic circuits, an important class of quantum circuits, (2) efficiency, and (3) reliability. For efficiency, we introduce two optimizations and an efficient matrix representation. For reliability, we prove physical consistency, ensuring that QASMInfer’s inference results adhere to the physical principles of quantum computing. To simplify the proof, we introduce OpenQASMCore, a core language for OpenQASM, and perform exact inference for OpenQASM by desugaring it to OpenQASMCore. Our implementation and proof are fully mechanized in the Coq proof assistant. Testing six real-world QSSs using QASMInfer revealed 31 bugs, including 20 non-crash bugs, demonstrating QASMInfer’s effectiveness as a testing oracle.

The conformance testing of programming language implementations is crucial to support correct and consistent execution environments. Because manually maintaining conformance tests for real-world programming languages is cumbersome and labor-intensive, researchers have presented various ways to make conformance tests effective and efficient. One such approach is to use graph coverage, one of the most widely-used coverage criteria, to generate tests that reach different parts of a mechanized language specification. Since mechanized specifications use functions or inductive definitions to describe the semantics of language features, traditional graph coverage criteria for software work as they are. However, they may not produce high-quality conformance tests because language implementations often have specialized execution paths for different features, even when their semantics descriptions use the same functions. Traditional graph coverage may not distinguish test requirements of such language features, which degrades the quality of conformance testing. Similarly, it may not distinguish test requirements of different parts of the same language feature when their semantics descriptions use the same functions. We present feature-sensitive (FS) coverage as a novel coverage criterion to generate high-quality conformance tests for language implementations. It is a general extension of graph coverage, refining conventional test requirements using the innermost enclosing language features. We also introduce feature-call-path-sensitive (FCPS) coverage, a variant of FS coverage, and extend both coverage criteria using the 𝑘-limiting approach. To evaluate the effectiveness of the new coverage criteria for language implementations, we apply them to a mechanized specification of JavaScript. We extend JEST, the state-of-the-art JavaScript conformance test synthesizer using coverage-guided mutational fuzzing, with various FS and FCPS coverage criteria. For the latest JavaScript language specification (ES13, 2022), our tool automatically synthesizes 237,981 conformance tests in 50 hours with five coverage criteria. We evaluated the conformance of eight mainstream JavaScript implementations (four engines and four transpilers) with the synthesized conformance tests and discovered bugs in all of them. The tool detected 143 distinct conformance bugs (42 in engines and 101 in transpilers), 85 of which were confirmed by the developers and 83 of which were newly discovered bugs.

Physical layer security is a useful tool to prevent illegal wiretapping to confidential information. In this paper, we consider a generalized model of conventional physical layer security, referred as hierarchical information accessibility (HIA). A main feature of the HIA model is that a network has a hierarchy in information access, wherein decoding feasibility is determined by each user’s priority. Under this HIA model, we formulate a sum secrecy rate maximization problem with regard to precoding vectors. This problem is challenging since multiple non-smooth functions are involved into the secrecy rate to fulfill the HIA conditions and also the problem is non-convex. To address the challenges, we approximate the minimum function by using the LogSumExp technique, thereafter obtain the first-order optimality condition. One key observation is that the derived condition is cast as a functional eigenvalue problem, where the eigenvalue is equivalent to the approximated objective function of the formulated problem. Accordingly, we show that finding a principal eigenvector is equivalent to finding a local optimal solution. To this end, we develop a novel method called generalized power iteration for HIA (GPI-HIA). Simulations demonstrate that the GPI-HIA significantly outperforms other baseline methods in terms of the secrecy rate.

In this paper, we consider a hierarchical information accessibility (HIA) model, which generalizes conventional physical layer security. In the considered model, multiple layers with different security priorities are assumed, where only the users in a higher priority layer are permitted to decode the message intended to lower priority layers. To maximize the sum secrecy rate of the considered system, we formulate an optimization problem with regard to precoders. To solve the formulated problem, we first approximate the objective function by using the LogSumExp technique and show that finding a local optimum is equivalent to finding a leading eigenvector of the first-order optimality condition of the reformulated problem. Accordingly, we propose a novel algorithm called generalized power iteration for hierarchical information accessibility (GPI-HIA) to obtain a solution. Via simulations, we demonstrate that the proposed method significantly outperforms other baseline schemes under the considered HIA scenario.