Some Size and Structure Metrics for Quantum Software

The NOT gate works on a single qubit. It can exchange the coefficients of two basis vectors:

$NOT(\alpha|0\rangle+\beta|1\rangle)=\alpha|1\rangle+\beta|0\rangle$

A single input-output quantum gate can be represented by a $2\ \times\ 2$ matrix. The state of a quantum state after passing through the quantum gate is determined by the value of the quantum state vector left-multiplied by the quantum gate matrix. The quantum gate matrix corresponding to the NOT gate is

$$X=\begin{bmatrix}0&1\\ 1&0\end{bmatrix}$$

$$X\begin{bmatrix}\alpha\\ \beta\end{bmatrix}=\begin{bmatrix}0&1\\ 1&0\end{bmatrix}\begin{bmatrix}\alpha\\ \beta\end{bmatrix}=\begin{bmatrix}\beta\\ \alpha\end{bmatrix}$$

The Hadamard gate also works on a single qubit, which can decompose existing quantum states according to its coefficients:

$H(\alpha|0\rangle+\beta|1\rangle)=\frac{\alpha+\beta}{\sqrt{2}}|0\rangle+\frac{\alpha-\beta}{\sqrt{2}}|1\rangle$

Computer programs are full of conditional judgment statements: if so, what to do, otherwise, do something else. In quantum computing, we also expect that the state of one qubit can be changed by another qubit, which requires a quantum gate with multiple inputs and outputs. The following is the controlled-NOT gate (CNOT gate). It has two inputs and two outputs. If the input and output are taken as a whole, this state can be expressed by

$$\alpha|00\rangle+\beta|01\rangle+\gamma|10\rangle+\theta|11\rangle$$

where $|00\rangle$, $|01\rangle$, $|10\rangle$, $|11\rangle$ are column vectors of length 4, which can be generated by concatenating $|0\rangle$ and $|1\rangle$. This state also needs to satisfy the normalization conditions, that is

$$|\alpha|^{2}+|\beta|^{2}+|\gamma|^{2}+|\theta|^{2}=1$$

The CNOT gate is two-qubit operation, where the first qubit is usually referred to as the control qubit and the second qubit as the target qubit. When the control qubit is in state —0$\rangle$, it leaves the target qubit unchanged, and when the control qubit is in state —1$\rangle$, it leaves the control qubit unchanged and performs a Pauli-X gate on the target qubit. It can be expressed in mathematical formulas as follows:

Quantum circuits, also known as quantum logic circuits, are the most commonly used general-purpose quantum computing models, which represent circuits that operate on qubits under an abstract concept. A quantum circuit is a collection of interconnected quantum gates. The actual structure of quantum circuits, the number and the type of gates, and the interconnection scheme, are all determined by the unitary transformation $U$, performed by the circuit. The result of a quantum circuit can be read out through quantum measurements.

As we know, the most commonly used measure of source code program length is the number of lines of code (LOC). LOC measure can be used to predict the quality and reliability of software productions. Similarly, for quantum software, we may also consider some LOC measures to measure the internal attribute of the software, specifically related to the quantum attributes. Let $Q$ be a quantum program, some basic LOC measures for $Q$ can be defined as follows:

• •

  The number of lines of code in $Q$

• •

  The number of lines of code concerning the quantum gate operations in $Q$

• •

  Number of lines of code related to the quantum operations in $Q$

• •

  Number of lines of code related to the quantum gate operations in $Q$

• •

  Number of lines of code related to the quantum measurements in $Q$

• •

  Number of qubits used in $Q$

• •

  Number of gates used in $Q$

Halstead introduces some size measures to measure the complexity of a classical program. According to Halstead, ”a computer program that implements an algorithm is considered to be a collection of tokens that can be divided into operators or operands.” Halstead observes that software measures should reflect how algorithms are implemented in different programming languages and independent of the platform and language used. These measures should be computable statically from the source code of the program.

Let $P$ be a program which is a collection of tokens, classified as either operators or operands, then some basic numbers can be defined as follows:

• •

  $\mu_{1}$: the number of unique operators in $P$

• •

  $\mu_{2}$: the number of unique operands in $P$

• •

  $N_{1}$: the total occurrences of operators in $P$

• •

  $N_{2}$: the total occurrences of operands in $P$

• •

  The length $N$ of $P$ is defined as $N=N_{1}+N_{2}$

• •

  The vocabulary $\mu$ of $P$ is defined as $\mu=\mu_{1}+\mu_{2}$

• •

  The estimated length $N_{\scriptscriptstyle E}$ of $P$ can be denoted as
  $N_{\scriptscriptstyle E}=\mu_{1}\log_{2}\mu_{1}+\mu_{2}\log_{2}\mu_{2}$

• •

  The volume $V$ of $P$ is defined as $V=N\times\log_{2}\mu$

• •

  The difficulty $D$ of $P$ is defined as $D=\frac{\mu_{1}}{2}\times\frac{N_{2}}{\mu_{2}}$

• •

  The effort $E$ of $P$ is defined as $E=D\times V$

A typical quantum program usually consists of two types of instructions: classical instructions that operate on the state of classical bits and apply conditional statements, and quantum instructions that operate on the state of qubits and measure the qubit values.

Let $Q$ be a quantum program, we can define some basic numbers related to the quantum operations in $Q$ as follows:

• •

  $\eta_{1}$: the number of unique quantum gate operators in $Q$

• •

  $\eta_{2}$: the number of unique quantum gate operands in $Q$

• •

  $N_{\scriptscriptstyle Q1}$: the total occurrences of quantum gate operators in $Q$

• •

  $N_{\scriptscriptstyle Q2}$: the total occurrences of quantum gate operands in $Q$

Based on these numbers, we can extend Halstead’s measures of classical software to the domain of quantum software by counting the total numbers of $Q$, which consists of classical and quantum statements, respectively, and have the following extended measures.

• •

  The length $N_{\scriptscriptstyle Q}$ of $Q$ is defined as $N_{\scriptscriptstyle Q}=N_{\scriptscriptstyle Q1}+N_{\scriptscriptstyle Q2}$

• •

  The vocabulary $\eta$ of $Q$ is defined as $\eta=\eta_{1}+\eta_{2}$

• •

  The estimated length $N_{\scriptscriptstyle QE}$ of $Q$ can be estimated from $N_{\scriptscriptstyle QE}=\eta_{1}\log_{2}\eta_{1}+\eta_{2}\log_{2}\eta_{2}$

• •

  The volume $V_{\scriptscriptstyle Q}$ of $Q$ may be defined as $V_{\scriptscriptstyle Q}=N_{\scriptscriptstyle Q}\log_{2}\eta$

• •

  The difficulty $D_{\scriptscriptstyle Q}$ of $Q$ is defined as $D_{\scriptscriptstyle Q}=\frac{\eta_{1}}{2}\times\frac{N_{\scriptscriptstyle Q2}}{\eta_{2}}$

• •

  The effort $E_{\scriptscriptstyle Q}$ of $Q$ is defined as $E_{\scriptscriptstyle Q}=D_{\scriptscriptstyle Q}\times V_{\scriptscriptstyle Q}$

Architectural design defines a collection of quantum software components, their functions, and their interactions (interfaces) to establish a framework for developing a quantum software system. The software architecture of the system defines its high-level structure, revealing its overall organization as a set of interacting components [perry1992foundations, mary1996software]. A well-defined architecture allows an engineer to reason about system properties at a high level of abstraction. We can measure the size of a quantum architectural design based on formal architectural specifications and architectural patterns.

Like classical ADLs, we can use a quantum architectural description language (qADL), an extension of a classical ADL to formally specify the architectures of a quantum software system, to support the architectural-level design of quantum systems. A qADL can specify a quantum system’s architecture with those mechanisms, including specifications of classical components with interfaces and connections between interfaces (already provided in classical ADLs), specifications of quantum components, and specifications of connections between classical and quantum components.

Let $S$ be the formal architectural specification of a quantum software architecture, which consists of a group of components and the connectors between components, and we can define some general architectural size measures for $S$ as follows:

• •

  Number of all components and connectors in $S$

• •

  Number of all components in $S$

• •

  Number of all connectors in $S$

• •

  Number of all quantum components in $S$

• •

  Number of all connectors between quantum components in $S$

• •

  Number of all connectors between a quantum component and a classical component in $S$

Like classical architectural patterns, we can also identify some quantum architectural patterns for supporting quantum software design. Based on these quantum architectural patterns, we can define some size measures at the architectural design level as follows:

• •

  Number of different architectural patterns used in a quantum architectural design

• •

  Number of architectural pattern realizations for each architectural pattern type

• •

  Number of different quantum architectural patterns used in a quantum architectural design

• •

  Number of quantum architectural pattern realizations for each quantum architectural pattern type

Detailed design refines and expends the architectural design to describe the internals of the quantum software components (the algorithms, processing logic, data structures, and data definitions). Similar to classical design patterns, we can also identify some quantum design patterns for quantum software.

Let $D$ be a design for a quantum software system, and we can define some general size measures in terms of design patterns in $D$

• •

  Number of different design patterns used in $D$

• •

  Number of design pattern realizations for each pattern type in $D$

Moreover, we can also define some size measures that are specific to quantify the quantum attributes in terms of quantum design patterns in $D$ as follows:

• •

  Number of different quantum design patterns used in $D$

• •

  Number of quantum design pattern realizations for each pattern type in $D$