一个基于模式匹配的电路重写框架
-
摘要:研究背景
量子计算近年来吸引了越来越多的注意,因为它为有效解决一些重要的问题提供了可能性,如整数分解、非结构化搜索和求解线性方程。近年来,随着量子计算的普及,许多公司、大学和机构一直在积极致力于开发量子计算机系统的原型。例如,2019年,谷歌宣布实现量子霸权,开发了53量子比特量子处理器“Sycamore”。2021 年 11 月,IBM 推出了其新的 127 量子比特“Eagle”处理器,其规模使经典计算机无法可靠地模拟,而增加的量子比特数量使用户能够在新的复杂程度上探索问题。2022 年 6 月,Xanadu 展示了其可编程光子处理器的量子计算优势,该处理器在 216 个压缩模式下实现了高斯玻色子采样。这些系统称为嘈杂的中等规模量子系统(NISQ)。
目的量子算法的实现依赖于根据量子处理器进行的特定量子编译。然而,在不同的物理环境中实现量子比特并操纵量子比特的方式不同。这些差异导致了不同的通信方法和连接拓扑,每个供应商都实现了自己的一套原始门。因此,量子电路的跨平台编译必须从一个平台移植到另一个平台。此外,由于量子处理器支持的门类型是有限的,因此在量子处理器上执行量子电路之前,当一些高级门被分解为低级门时,量子电路也可能被重写。
方法我们提出了一个基于模式匹配的框架来重写量子电路,称为QRewriting。它利用了使用符号序列的量子电路的新表示。与使用有向无环图的传统方法不同,新的表示使我们能够轻松识别非连续出现但可规约的模式电路。然后,将模式匹配问题转化为寻找不同子序列的问题,并提出一种基于多项式时间动态规划的模式匹配和替换算法。
结果我们将QRewriting与基于模式匹配的量子电路优化框架PaF进行了比较。相较于PaF,QRewriting优化后的电路在 1-qubit门数量、2-qubit门数量、总门数和深度方面平均减少了5.2%、57.0%、17.4%和26.5%。在时间方面,QRewriting 比 PaF 快约 5 倍。除此之外,我们还在算术和Toffoli基准上进行了重写测试。从实验数据可以看出从门集 GIBM 到门组 GSur 的电路重写,门数最多可减少 52%,深度最多可减少 49%。
结论我们引入了一种新的量子电路表示,将电路的模式匹配简化为寻找不同子序列的问题。 为此提出了一种基于动态编程的算法,以匹配目标电路中的图形电路。为了解决替换冲突,我们提出了三种用于生成替换调度器的策略和多项式时间替换算法。量子电路优化是一项很有前景的研究方向与此相关的还有量子电路编译问题。
Abstract:The realization of quantum algorithms relies on specific quantum compilations according to the underlying quantum processors. However, there are various ways to physically implement qubits and manipulate those qubits in different physical devices. These differences lead to different communication methods and connection topologies, with each vendor implementing its own set of primitive gates. Therefore, quantum circuits have to be rewritten or transformed in order to be transplanted from one platform to another. We propose a pattern matching based framework for rewriting quantum circuits, called QRewriting. It takes advantage of a new representation of quantum circuits using symbolic sequences. Unlike the traditional approach using directed acyclic graphs, the new representation allows us to easily identify the patterns that appear non-consecutively but are reducible. Then, we convert the problem of pattern matching into that of finding distinct subsequences and propose a polynomial-time dynamic programming based pattern matching and replacement algorithm. We develop a rule library for basic optimizations and rewrite the arithmetic and Toffoli circuits from a commonly used gate set to the gate set supported by the Surface-17 quantum processor. Compared with a state-of-the-art quantum circuit optimization framework PaF optimized on the BIGD benchmarks, QRewriting further reduces the depth and the gate count by an average of 26.5% and 17.4%, respectively.
-
Keywords:
- pattern matching /
- quantum circuit rewriting /
- subsequence
-
1. Introduction
Quantum computing has attracted increasing interest in the last decades since it provides the possibility to efficiently solve important problems such as integer factorization[1], unstructured search[2], and linear equations[3].
In recent years, with the popularity of quantum computing, many companies, universities, and institutes have been actively working to develop prototypes of quantum computers. For example, in 2019, Google announced the realization of quantum supremacy, the development of the 53-qubit quantum processor “Sycamore”[4]. In November 2021, IBM unveiled its new 127-qubit “Eagle” processor whose scale makes it impossible for a classical computer to reliably simulate, and the increased qubit count allows users to explore problems at a new level of complexity
1 . In June 2022, Xanadu demonstrated a quantum computational advantage with a programmable photonic processor that realized Gaussian boson sampling on 216 squeezed modes[5]. These systems are referred to as noisy intermediate-scale quantum systems[6] and have small qubit counts, restricted connectivity, and high gate error rates. The duration of a physical quantum gate is roughly 10 ns–800 ns, if the fidelity of physical gates achieves at least 99%[7]. At present, the coherence time of each physical qubit is 1 μs–150 μs and only a limited set of gates can be realized with relatively high fidelity on a quantum device. Each quantum processor may support a specific universal set of 1-qubit and 2-qubit gates, which are called primitive gates[7]. Table 1 lists three gate sets: GCom, GIBM, and GSur, where GCom is a commonly used gate set[8], GIBM is implemented by the IBM Q series[9], and GSur is used by the Surface-17 quantum processor[10].Table 1. Three Gate Sets for Different ScenariosGate Set Symbol GCom[8] {\bf{H}}, {\bf{X}}, {\bf{Y}}, {\bf{Z}}, {\bf{S}}, {\bf{S}}^{\dagger}, {\bf{T}}, {\bf{T}}^{\dagger}, {\boldsymbol{R}}_{\rm z}(\theta), {\bf{CX }} G_{ {\rm{IBM}}}[9] {\boldsymbol{U }}_1(\theta), \ {\boldsymbol{U }}_2(\alpha,\ \lambda),\ {\boldsymbol{U }}_3(\theta,\ \alpha,\ \lambda), \ {\bf{CX }} G_{ {\rm{Sur}}}[10] {\bf{X}}, {\bf{Y}}, {\boldsymbol{R}}_{\rm{x}}(\theta), {\boldsymbol{R}}_{\rm{y}}(\theta), {\bf{CZ}} The realization of quantum algorithms relies on specific quantum compilations, which mainly focus on the number of inserted quantum gates[11, 12] or the fidelity of the compiled quantum circuits[13, 14]. However, there are various ways to physically implement qubits in different physical devices and manipulate these qubits. These differences lead to different communication methods and connection topologies, with each vendor implementing its own set of primitive gates. Therefore, quantum circuits have to be transplanted from one platform to another. In addition, since the gate types supported by a quantum processor are limited, quantum circuits may also be rewritten when some high-level gates are decomposed into low-level gates before quantum circuits execute on the quantum processor.
Converting a quantum circuit supported by one gate set to a quantum circuit supported by another gate set with respect to some rules is called quantum circuit rewriting. Usually, a rule is in the form {\cal{C}}_{\rm{p}} = {\cal{C}}_{\rm{s}} , where {\cal{C}}_{\rm{p}} is a fragment of a circuit whose behavior is the same as that of the fragment {\cal{C}}_{\rm{s}} . We call {\cal{C}}_{\rm{p}} a pattern circuit and {\cal{C}}_{\rm{s}} a substitution circuit. In this paper, we refer to the circuit to be rewritten as the target circuit. Motivated by the aforementioned requirements, our approach consists of two key steps: the first is to identify the patterns in the target circuit, the second is to replace them with semantically equivalent substitution circuits. For that purpose, we first introduce a new representation of quantum circuits using symbolic sequences. Unlike the traditional way of using directed acyclic graphs (DAGs) based on the execution dependencies of the circuit[15], the new representation allows us to easily identify the patterns that appear non-consecutively but are reducible. In the case that a fragment of a circuit can be matched by several different rules, we encounter a replacement conflict and need to resolve it with an appropriate policy. We propose three policies for generating schedulers to cope with replacement conflicts. One policy is precise in the sense that it will consider all the replacement candidates of a conflict set. In the worst case, its time complexity is exponential. For a large-scale circuit, we need to make a trade-off between the quality of the generated circuit and the time it takes. Therefore, for large-scale circuits, we propose a greedy policy to handle replacement conflicts and a stochastic policy to show that better policies exist.
The main contributions of this paper are summarized below.
● We introduce a new representation of quantum circuits, which can easily identify the patterns that appear non-consecutively but are reducible in the target circuits.
● We present a polynomial-time dynamic programming based pattern matching and replacement algorithm.
● We propose three policies for generating schedulers to deal with replacement conflicts.
● We develop a rule library for basic optimizations.
The rest of the paper is structured as follows. Section 2 introduces the related work. Section 3 recalls the basic notations about quantum computing. Section 4 proposes a new representation of quantum circuits. Section 5 discusses the design of the pattern matching based quantum circuit rewriting framework. Section 6 shows two case studies. Section 7 evaluates QRewriting by using the BIGD[16] benchmarks and a set of benchmark circuits[17] consisting of arithmetic circuits and implementations of multi-controlled Toffoli gates. Finally, Section 8 gives the conclusion.
2. Related Work
Several quantum circuit optimization compilers have recently been proposed to compile a quantum circuit to various processors. For example, Qiskit
2 and t | ket \rangle [18] support generic gate sets, and Quilc3 is tailored for the Rigetti Agave quantum processor. There are several optimizers that automatically discover patterns[19-22]. QRewriting aims to rewrite quantum circuits between different processors according to a given rule set, mainly focusing on pattern matching and replacement.Pattern matching is widely used in circuit optimization. For example, many algorithms have employed peephole optimization and pattern matching to optimize circuits. Peephole optimization identifies small sets of gates and replaces them with equivalent sets that have better performance[13, 23]. Exact matching is only feasible for small-scale and medium-scale circuits[24]. Heuristics are often used in large-scale circuits, but they cannot ensure optimal results[25, 26]. Prasad et al. and Soekens et al. showed how to find optimal quantum circuits for all 3-qubit functions[27, 28]. Nam et al. proposed five optimization subroutines[17]. Murali et al. developed the first multi-vendor quantum computer compiler which compiles from high-level languages to multiple real-system quantum computer prototypes, with device-specific optimizations[9]. The work of Chen et al. is the closest to ours, where a quantum circuit optimization framework based on pattern matching (PaF) was proposed[29]. It uses subgraph isomorphism to find a pattern circuit in the target quantum circuit according to a given rule description, and then replaces it with an equivalent one.
Previous work often treats a target circuit {\cal{C}} as a DAG, which is usually not unique because various gates may commute. The patterns that appear non-consecutively but are reducible cannot be directly identified by subgraph isomorphism in the DAG. It can integrate with commutation analysis to adjust the order of commuting gates with time complexity O(| {\cal{C}}|^{2}) , where | {\cal{C}}| is the length of the circuit {\cal{C}} .
In this paper, we introduce a new representation of quantum circuits, which can deal with non-consecutive patterns more conveniently. For quantum circuit rewriting, we propose a polynomial-time algorithm, which is based on dynamic programming to match and replace pattern circuits in the target circuit.
3. Preliminaries
In this section, we introduce some notions and notations of quantum computing. Let {\mathbb{Z}} and {\mathbb{C}} denote the sets of all integers and complex numbers, respectively.
Classical information is stored in bits, while quantum information is stored in qubits. Besides two basic states \left| {{\bf{0}}} \right\rangle and \left| {{\bf{1}}} \right\rangle , a qubit can be in any linear superposition state \left| {{\boldsymbol{\phi}}} \right\rangle = a\left| {{\bf{0}}} \right\rangle+b\left| {{\bf{1}}} \right\rangle , where a, b\in {\mathbb{C}} satisfy the condition |a|^{2}+|b|^{2} = 1 . State \left| {{\boldsymbol{\phi}}} \right\rangle is observed to be in state \left| {{\bf{0}}} \right\rangle with probability |a|^{2} and in state \left| {{\bf{1}}} \right\rangle with probability |b|^{2} .
A quantum gate acts on a collection of qubits, which are called the operation qubits of the gate. For example, the Hadamard ( {\bf{H}} ) gate is applied on one qubit, and the {\bf{CX }} gate is applied on two qubits. Its behavior is described as:
{\bf{CX}}(\alpha\left| {{\bf{0}}} \right\rangle\left| {{\boldsymbol{\psi}}} \right\rangle+\beta\left| {{\bf{1}}} \right\rangle\left| {{\boldsymbol{\phi}}} \right\rangle) = \alpha\left| {{\bf{0}}} \right\rangle\left| {{\boldsymbol{\psi}}} \right\rangle+\beta\left| {{\bf{1}}} \right\rangle({\bf{X}} \left| {{\boldsymbol{\phi}}} \right\rangle). That is, we apply an {\bf{X}} gate to the second qubit (called the target) if the first (the control) is in the state \left| {{\bf{1}}} \right\rangle , and the identity transformation otherwise, where \left| {{\boldsymbol{\psi}}} \right\rangle and \left| {{\boldsymbol{\phi}}} \right\rangle are the states of the second qubit. Two other gates which are relevant include the 3-qubit Toffoli gate {\bf{CCX}} and the double-controlled phase gate {\bf{CCZ}} . Likewise, the {\bf{CCX}} and {\bf{CCZ}} gates apply {\bf{X}} and {\bf{Z}} gate, respectively, when the control qubits are in state \left| {{\bf{1}}} \right\rangle .
In a quantum circuit, each line represents a wire. The wire does not necessarily correspond to a physical wire, but may correspond to the passage of time or a physical particle that moves from one location to another through space. The interested reader can find more details of these gates in the standard textbook[8]. The execution order of a quantum logical circuit is from left to right. The width of a quantum circuit refers to the number of qubits in the quantum circuit. The depth of a quantum circuit refers to the number of layers of gates that are executable in parallel. We refer to a quantum circuit with a depth of less than 100 as a small-scale circuit, a quantum circuit with a depth of more than
1000 as a large-scale circuit, and the rest as medium-scale circuits.4. Circuit Representation
In this section, we define a new representation of quantum circuits and the pattern matching condition, which easily identifies the patterns that appear non-consecutively but are reducible. Based on that, we will state the quantum circuit rewriting problem considered in the paper.
Definition 1. A gate is represented by a triple (\gamma, \sigma, \alpha) , where
● \gamma is the symbol of a gate type,
● \sigma is a finite sequence of operation qubits for a gate,
● \alpha is a finite sequence of rotation angles for a gate.
A quantum circuit {\cal{C}} is a sequence of triples (\gamma_0,\ \sigma_0,\ \alpha_0)(\gamma_1,\ \sigma_1,\ \alpha_1) \ldots (\gamma_{n-1},\ \sigma_{n-1},\ \alpha_{n-1}) , and the length of the circuit is denoted by | {\cal{C}}| . The gate sequence \Gamma_ {\cal{C}} of quantum circuit {\cal{C}} is a symbolic sequence of gate types obtained by projecting each element of {\cal{C}} to its first component, i.e., \Gamma_ {\cal{C}} = “\gamma_0\gamma_1\ldots \gamma_{n-1} ”. The new representation of a rule is a pair r = ( {\cal{C}}_{\rm{p}}, \ {\cal{C}}_{\rm{s}}) , consisting of a pattern circuit {\cal{C}}_{\rm{p}} and a substitution circuit {\cal{C}}_{\rm{s}} . For simplicity, if the sequence is empty \epsilon , we ignore it. Table 2 lists some of the commonly used quantum gates, their distinct aliases, and the corresponding circuit symbols.
Table 2. Symbols of Gates and Distinct AliasesGate Aliase Circuit {\bf{I}} “I” {\bf{H}} “h” {\bf{X}} “x” {\bf{Y}} “y” {\bf{Z}} “z” {\bf{T}} “t” {\bf{T}}^{\dagger} “T” {\bf{S}} “s'' {\bf{S}}^{\dagger} “S” {{\boldsymbol{R}}}_{\rm{x}} “X' {{\boldsymbol{R}}}_{\rm{y}} “Y” {{\boldsymbol{R}}}_{\rm z} “Z” {\bf{CX }} “c” {\bf{CZ}} “C” {\bf{CCX}} “E” {\bf{CCZ}} “F” Example 1. We illustrate the symbolic sequences of the circuit obtained by using the patterns in Fig.1 to rewrite target circuit {\cal{C}}_{\rm{t}} in Fig.2(a) as an example. The new representation of the quantum circuit is
\begin{array}{l} {\cal{C}}_{\rm{t}} = ( { {“{\rm{x}}”}},\ q_2)({ {“{\rm{x}}”}},\ q_2)({ {“{\rm{c}}”}},\ q_0q_1)({ {“{\rm{c}}”}},\ q_0q_2)\\ \;\;\;\;\;\;\;\; ({ {“{\rm{c}}”}},\ q_0q_1) ( { {“{\rm{x}}”}},\ q_2)({ {“{\rm{x}}”}},\ q_0), \end{array} and its gate sequence is represented by \Gamma_{\rm{t}} = { {“{\rm{xxcccxx}}”}} . We can make use of the rule set {\cal{R}} = \{ r_0,\ r_1,\ r_2,\ r_3\} in Fig.1 to rewrite the circuit, where
r_0 = ( ({ {“{\rm{x}}”}},\ q_0)({ {“{\rm{x}}”}},\ q_0),\ ({ {“{\rm{I}}”}},\ q_0)),\ r_1 = ( ({ {“{\rm{c}}”}},\ q_0q_1)({ {“{\rm{c}}”}},\ q_0q_1),\ ({ {“{\rm{I}}”}},\ q_0)({ {“{\rm{I}}”}},\ q_1)), \begin{array}{l} r_2 = (({ {“{\rm{c}}”}},\,q_0q_1)({ {“{\rm{c}}”}},\,q_1q_2)({ {“{\rm{c}}”}},\,q_0q_1),\,({ {“{\rm{c}}”}},\,q_0q_2)\\\;\;\;\;\;\;\;\;( { {“{\rm{c}}”}},\,q_1q_2)),\, \end{array} r_3 = ( ({ {“{\rm{x}}”}},\ q_1)({ {“{\rm{c}}”}},\ q_0q_1)({ {“{\rm{x}}”}},\ q_1),\ ({ {“{\rm{c}}”}},\ q_0q_1)). To facilitate the description of pattern matching, we introduce the following definitions.
Definition 2[30]. Let \Gamma and \Gamma' be two sequences. We say \Gamma' is a subsequence of \Gamma , if there exist indices 0 \leqslant i_0 <\ldots< i_{|\Gamma'|-1} < |\Gamma| such that \Gamma[i_{k}] = \Gamma'[k] for all k \in [0,\ |\Gamma'|-1] .
The subsequence set is a set of distinct subsequences of the pattern circuit in the target circuit. We do not distinguish the indices from the gates to which the indices correspond in the quantum circuit. Suppose \Gamma is a gate sequence. Then \Gamma[i:j] means to take the fragment of \Gamma from index i to j . If j is not specified, it takes the suffix of \Gamma from index i . Supposing that \Gamma' is a subsequence of \Gamma , we write \Gamma \setminus \Gamma' to indicate the subsequence of \Gamma obtained by removing all occurrences of \Gamma' .
Example 2. Continuing to consider Example 1, the gate sequences and subsequence sets of the pattern circuits in rule set {\cal{R}} are given as follows:
● { {“{\rm{xx}}”}} : \{[{0,\ 1}]\},
● { {“{{\rm{cc}}}”}} : \{[{2,\ 4}]\},
● { {“{{\rm{ccc}}}”}} : \emptyset,
● { {“{{\rm{xcx}}}”}} : \{[{1, \ 3, \ 5}]\}.
Definition 3 (Qubit Mapping). Given two qubit sets Q and Q' , a qubit mapping function f is a bijective function between the qubit sets Q and Q' .
Definition 4 (Qubit State Independence). Let {\cal{C}}_{\rm{t}} , {\cal{C}}_{\rm{p}} be two circuits with gate sequences \Gamma_{\rm{t}} , \Gamma_{\rm{p}} , respectively. Suppose a subsequence \Gamma_{\rm{t}}' = \{i_0,\ \ldots,\ i_{\rm{l}}\} of \Gamma_{\rm{t}} that can match \Gamma_{\rm{p}} . We say the qubit state in \Gamma_{\rm{t}}' is independent w.r.t. \Gamma_{\rm{t}}[i_0:i_{\rm{l}}] \setminus \Gamma_{\rm{t}}' , if the control qubit set in \Gamma_{\rm{t}}' does not intersect with the target qubit set of the gates in \Gamma_{\rm{t}}[i_0:i_{\rm{l}}] \setminus \Gamma_{\rm{t}}' , and vice-versa.
Definition 5 (Pattern Matching). Let {\cal{C}}_{\rm{t}} and {\cal{C}}_{\rm{p}} be a target circuit and a pattern circuit with gate sequences \Gamma_{\rm{t}} , \Gamma_{\rm{p}} , respectively. We say {\cal{C}}_{\rm{p}} matches {\cal{C}}_{\rm{t}} if the following two conditions hold:
● \Gamma_{\rm{t}} has a subsequence that can match \Gamma_{\rm{p}} up to a qubit mapping function;
● the qubit sets of the subsequence and the pattern circuit satisfy the qubit mapping function and the qubit state independence condition.
Example 3. We continue Example 2 to show the difference between the new representation of quantum circuits and the DAG representation. Suppose the gates of target circuit {\cal{C}}_{\rm{t}} (resp. pattern circuit of r_1 ) from left to right are named g_0 – g_6 (resp. g_0' – g_1' ). Fig.3(a) is the DAG representation of the circuit fragment g_2 – g_4 and Fig.3(c) is the DAG representation of the pattern circuit of r_1 . We can see that Fig.3(a) has no subgraph isomorphic to Fig.3(c). The gates g_2 and g_3 in Fig.3(a) are exchanged by commutation analysis to obtain Fig.3(b), which contains a subgraph isomorphic to Fig.3(c). The symbolic sequence of the circuit {\cal{C}}_{\rm{t}} can directly match the pattern circuit of r_1 , i.e., the gates g_2 and g_4 . It satisfies the qubit mapping function { f ( q_0) = q_0 , f(q_1) = q_1 } and the qubit state independence condition. Therefore, circuit {\cal{C}}_{\rm{t}} can be rewritten as: ({ {“{\rm{x}}”}},\ q_2) ({ {“{\rm{x}}”}},\ q_2) ({ {“{\rm{c}}”}},\ q_0q_2)({ {“{\rm{x}}”}}, q_2)({ {“{\rm{x}}”}},\ q_0) .
Definition 6. For a given target circuit {\cal{C}}_{\rm{t}} and a rule r = ( {\cal{C}}_{\rm{p}},\ {\cal{C}}_{\rm{s}}) , a replacement candidate is a triple (D,\ r,\ e) , where
● D is a subsequence of the target circuit {\cal{C}}_{\rm{t}} that can match the pattern circuit {\cal{C}}_{\rm{p}} ,
● r is a rule,
● e \in {\mathbb{Z}} is a conflict index, with the default value being -1 .
Definition 7. A target circuit has a replacement conflict if an index of the target circuit appears more than once in the subsequence set.
The replacement candidates for a replacement conflict form a conflict set. A replacement scheduler is a set of replacement candidates for different indices.
Example 4. Continuing to consider Example 3, we see that the subsequence set of sequence “ {\rm{cc}} ” is \{[{2,\ 4}]\} . The subsequence [{2,\ 4}] appears non-consecutively in the sequence \Gamma_{\rm{t}} . The gate ({ {“{\rm{x}}”}}, q_2) appears in both the subsequence sets of “ {\rm{xx}} ” and “ {\rm{xcx}} ”, which means that in the target circuit, different rules may be matched at the same index. Two schedulers are given as follows:
\begin{array}{l} s' = \{ ([{0,\ 1}],\ r_0,\ 1),\ ([{2,\ 4}],\ r_1)\},\ \\ s'' = \{ ([{1,\ 3,\ 5}],\ r_3,\ 1),\ ([{2,\ 4}],\ r_1)\}. \end{array} The scheduler s' (resp. s '') replaces the gates in the sequence [{0,\ 1}] (resp. [{1,\ 3,\ 5}] ) using the substitution circuit of r_0 (resp. r_3 ). After one of the schedulers is applied, we get the circuit in Fig.2(b) or Fig.2(c). Different schedulers result in different gate counts or depths of the rewritten circuits. The circuits rewritten by scheduler s' or s '' have the same gate counts but with depths 2 and 3, respectively. In both schedulers, the first element has the component 1 , which is an index to indicate where the conflict takes place.
We are now ready to state the following problem.
Problem 1. Given two gate sets G_1 , G_2 and a rule set {\cal{R}} that expresses the equivalence of each gate in G_1 in terms of elements of G_2 , how can one rewrite a quantum circuit supported by a gate set G_1 to a quantum circuit supported by G_2 ?
By using the new representation of quantum circuits, we reduce the above problem to find distinct subsequences of the pattern sequence in the target sequence up to a qubit mapping function, and we use a qubit state independence condition to filter the obtained subsequences.
5. Quantum Circuit Rewriting
We propose a pattern matching based quantum circuit rewriting framework QRewriting. It consists of two steps: one matches the pattern circuit in the target circuit, and the other replaces it.
5.1 Pattern Matching Algorithm
We propose an algorithm based on dynamic programming to match the patterns in a rule set against a target circuit. Let {\cal{C}}_{\rm{t}} and {\cal{C}}_{\rm{p}} be the target and pattern circuits with gate sequences \Gamma_{\rm{t}} and \Gamma_{\rm{p}} , respectively. We consider the problem of finding the distinct subsequences of the pattern sequence \Gamma_{\rm{p}} in the target sequence \Gamma_{\rm{t}} . The obtained subsequences only match the gate types, and thus we need to check whether the operation qubits in the subsequences satisfy the qubit mapping function and the qubit state independence condition.
The input of Algorithm 1 is a target circuit {\cal{C}}_{\rm{t}} and a rule set {\cal{R}} , and the output is a set of replacement candidates {\cal{M}} . The function subseq (\Gamma_{\rm{t}},\, \Gamma_{\rm{p}},\, \delta) in Algorithm 2[31] uses a dynamic programming algorithm to compute the distinct subsequences of \Gamma_{\rm{t}} that can match \Gamma_{\rm{p}} and returns the subsequence set to set D . The function check_qubit_condition (D, \, {\cal{C}}_{\rm{t}},\, r) checks whether the subsequences in D satisfy the qubit mapping function and the qubit state independence condition.
Algorithm 1. pattern_matching ( {\cal{C}}_{\rm{t}} , {\cal{R}} ) Input: a quantum circuit {\cal{C}}_{\rm{t}} and a rule set {\cal{R}} ; Output: a set of substitution candidate {\cal{M}} ; 1 {\cal{M}} \gets \emptyset ; 2 Let \Gamma_{\rm{t}} be the gate sequence of circuit {\cal{C}}_{\rm{t}} ; 3 for each r \in {\cal{R}} do 4 Let \Gamma_{\rm{p}} be the gate sequence of pattern circuit of r ; 5 D \gets subseq (\Gamma_{\rm{t}},\, \Gamma_{\rm{p}},\, \delta) ; 6 if {{check}}\_{{qubit}}\_{{condition}} (D,\, {\cal{C}}_{\rm{t}},\, r) then 7 {\cal{M}} \gets {\cal{M}} \cup\{(u,\, r,\, -1): u\in D\}; 8 return {\cal{M}} ; Algorithm 2. subseq (\Gamma_{\rm{t}},\, \Gamma_{\rm{p}}, \,\delta) Input: two sequences \Gamma_{\rm{t}} and \Gamma_{\rm{p}} , and a parameter \delta ; Output: a set of subsequences of \Gamma_{\rm{p}} ; 1 Let D be a sequence of length |\Gamma_{\rm{p}}|+1 and each element is an empty set; 2 Let \epsilon be an empty sequence and D[0]\leftarrow \{\epsilon\} ; 3 for i \gets 0 {\rm{to}} |\Gamma_{\rm{t}}| do 4 for j \gets \min(i,\,|\Gamma_{\rm{p}}|) {\rm{to}} 0 do 5 if \Gamma_{\rm{t}}[i]=\Gamma_{\rm{p}}[j] then 6 D[j+1]\gets D[j+1] \cup \{u. \text{append}(i):
u\in D[j]\ { \;{\rm{and}} }\;\ i-u[0]<\delta \} ;7 return D[|\Gamma_{\rm{p}}|+1] ; The input of function subseq (\Gamma_{\rm{t}},\, \Gamma_{\rm{p}}, \, \delta) consists of a target sequence \Gamma_{\rm{t}} , a pattern sequence \Gamma_{\rm{p}} , and a parameter \delta to limit the range of indices of \Gamma_{\rm{p}} in \Gamma_{\rm{t}} . The output is a set D[|\Gamma_{\rm{p}}|+1] recording the distinct subsequences of \Gamma_{\rm{t}} that can match \Gamma_{\rm{p}} . We use set D[j+1] to record the subsequences of \Gamma_{\rm{t}} that can match \Gamma_{\rm{p}}[0:j] . If the condition \Gamma_{\rm{t}}[i] = \Gamma_{\rm{p}}[j] is satisfied, there are subsequences of \Gamma_{\rm{t}}[0:i] that can match \Gamma_{\rm{p}}[0:j] . Line 6 updates set D[j+1] . To find the subsequence of \Gamma_{\rm{p}}[0:j] , we need to first calculate the subsequences of \Gamma_{\rm{p}}[0:j-1] . The update: D[j+1] \gets D[j+1] \cup \{u. {\rm append}(i): u\in D[j]\ {{\rm{and}} }\ i-u[0]<\delta \}\ is the Bellman equation[31], which is a necessary enabler of the dynamic programming algorithm. The time complexity of Algorithm 1 is O(| {\cal{R}}|\times |\Gamma_{\rm{p}}|\times |\Gamma_{\rm{t}}|) and the space complexity is O(|\Gamma_{\rm{p}}|) .
Example 5. Let us consider the quantum circuit in Fig.4(a) and the rule set {\cal{R}} = \{ r_0, r_1, r_2, r_3\} in Fig.1. The gate sequences of the target circuit and the pattern circuits are “{{\rm{xxxxcccxxxxxcccxxxxcccxxxcccxxxx}}} {{\text{xxccc}}} ”, “ {\rm{xx}} ”, “ {\rm{cc}} ”, “{{\rm{ccc}}} ”, and “ {\rm{xcx}} ”, respectively. The subsequence set of “ {\rm{cc}} ” is \{[{4,\ 5}],\ [{4,\ 6}],[{5, 6}], \ldots\}. The corresponding gates of the indices \{4,\ 5,\ 6\} in target circuit {\cal{C}}_{\rm{t}} are ({ {“{\rm{c}}”}},\ q_{13}q_2)({ {“{\rm{c}}”}},\ q_{9}q_{14})({ {“{\rm{c}}”}}, q_4q_{12}) . The subsequences [{4,\ 5}], [{4,\ 6}], [{5,\ 6}] do not satisfy the qubit mapping function condition. The function check_qubit_condition (D,\, {\cal{C}}_{\rm{t}},\, r) filters the subsequences and finally gets the subsequence set of “ {\rm{cc}} ” in the gate sequence of the target circuit, which is \{[{5,\ 12}],\ [{19,\ 25}]\} highlighted with dotted lines in Fig.4(a).
5.2 Replacement Algorithm
By Algorithm 1, we obtain all the subsequences of the pattern circuits in the target circuit. To resolve replacement conflicts, we propose three conflict resolution policies. They give rise to three variants of QRewriting called QPRewriting, QGRewriting, and QSRewriting, respectively. Note that QRewriting uses the greedy policy by default. Due to the decoherence of qubits, the lifetime of qubits is very short[32]. The execution time of a quantum circuit is determined by several factors such as the depth and the gate count of the quantum circuit. Here, we mainly use depth to select the optimal replacement scheduler.
● The precise policy calculates all the candidates when a replacement conflict occurs.
● The greedy policy chooses the candidate appearing first in the target circuit among the conflict set.
● The stochastic policy selects a candidate stochastically in the conflict set for the scheduler.
We propose an algorithm based on the breadth-first search to compute the replacement scheduler as shown in Algorithm 3. The input is a gate sequence \Gamma_{\rm{t}} and a set of replacement candidates {\cal{M}} . {\cal{S}} is a scheduler set, and queue {\cal{S}}_{\rm{q}} stores the sub-scheduler. Firstly, we push an empty scheduler \emptyset into queue {\cal{S}}_{\rm{q}} . Then, we loop queue {\cal{S}}_{\rm{q}} (lines 4–12), until it is empty. Function next_conflict (\Gamma_{\rm{t}}, \, {\cal{M}}, \, s) computes the next conflict index e in \Gamma_{\rm{t}} from the current conflict index to the end of \Gamma_{\rm{t}} . If there is no conflict at this index, we directly add the replacement candidate to s . Otherwise, we return the index. When arriving at the end of \Gamma_{\rm{t}} , we add scheduler s into {\cal{S}} . Line 10, according to the conflict policy, calculates the candidate set that has a conflict at index e in {\cal{M}} . Lines 11 and 12 append the replacement candidates to s and push it into queue {\cal{S}}_{\rm{q}} . Finally, we calculate the depth of the replaced circuit and return the scheduler with the smallest depth.
Algorithm 3. solve_conflicts (\Gamma_{\rm{t}}, \, {\cal{M}}) Input: a gate sequence \Gamma_{\rm{t}} and a set of replacement candidates {\cal{M}} ; Output: a replacement scheduler; 1 {\cal{S}} \gets \emptyset ; 2 Let {\cal{S}}_{\rm{q}} be a scheduler queue; 3 {\cal{S}}_{\rm{q}}. push (\emptyset) ; 4 while {\cal{S}}_{\rm{q}} is not empty do 5 s\gets {\cal{S}}_{\rm{q}}. pop(); 6 e \gets next_conflict (\Gamma_{\rm{t}}, \, {\cal{M}}, \, s) ; 7 if e=-1 then 8 {\cal{S}} \gets {\cal{S}} \cup \{s\} ; 9 continue; 10 V \gets compute the conflict set on index e ; 11 for each v \in V do 12 {\cal{S}}_{\rm{q}}. push (s\cup \{v\}) ; 13 return compute_depth ( {\cal{S}} ); The time complexity depends on the conflict policy. In the worst case, the precise policy is used and the worst time complexity is O(|V|^m) , where m is the number of conflicts and |V| is the size of the largest conflict set. When dealing with large-scale circuits, the precise policy is not scalable. Therefore we do not plan to demonstrate the precise policy in our experiments. The time complexity of both the greedy and stochastic policies are O(m|V|) .
Example 6. Continuing to consider Example 5, we show how to generate schedulers. Starting from the index e = 0 , we search for the next conflicting index e in {\cal{M}} . When e = 18 , the conflict set is \{([{10,\ 18}], r_0,\ 18),\ ([{18,\ 26,\ 31}],\ r_3,\ 18)\} . If the precise policy is used, we append scheduler s with the two candidates and put it into queue {\cal{S}}_{\rm{q}} . Then, the generated scheduler set {\cal{S}} = \{s',\ s''\} are given as follows:
\begin{array}{l} s' = \{ ([{0,\ 22}],\ r_0),\ ([{2,\ 13,\ 17}],\ r_3),\ ([{3,\ 9}],\ r_0),\ \\ \;\;\;\;\;\;\ \; ([{5,\ 12}],\ r_1),\ ([{10,\ 18}],\ r_0,\ 18),\ ([{15,\ 23}],\ r_0),\ \\ \;\;\;\;\;\;\ \; ([{16,\ 24}],\ r_0),\ ([{19,\ 25}],\ r_1)\},\ \\ s'' = \{ ([{0,\ 22}],\ r_0),\ ([{2,\ 13,\ 17}],\ r_3),\ ([{3,\ 9}],\ r_0),\ \\ \;\;\;\;\;\;\ \;\, ([{5,\,12}],\,r_1),\,([{18,\,26,\,31}],\,r_3,\,18),\,([{15,\,23}],\,r_0),\\ \;\;\;\;\;\;\ \; \, ([{16,\ 24}],\ r_0),\ ([{19,\ 25}],\ r_1)\}. \end{array} If we use the greedy policy, the replacement candidate ([{10,\ 18}],\ r_0,\ 18) is selected, and the generated scheduler is s' . If we use the stochastic policy, one of them is selected and the finally generated scheduler is either s' or s ''.
For the scheduler provided by Algorithm 3, we propose a replacement algorithm as shown in Algorithm 4, which reversely traverses each element of the scheduler and substitutes it according to the patterns. The input includes a target circuit {\cal{C}}_{\rm{t}} and a scheduler s . The output is a substitution circuit. Line 2 obtains the mapping relationship Q_{\rm{m}} of qubits between the subsequence of the target circuit and the pattern circuit, according to the qubit mapping function qubits_mapping (s_i) . Line 3 updates the gates on the target circuit with the substitution circuit one by one. If the substitution gate sequence is longer than the pattern gate sequence, the redundant gates are inserted after the index where the pattern circuit appears in the target circuit. Otherwise, the redundant locations are removed from the target circuit. The time complexity is O(m|s|) , where m is the maximum length of the pattern circuit, and |s| is the length of the scheduler s .
Algorithm 4. substitute( {\cal{C}}_{\rm{t}},\, s ) Input: a quantum circuit {\cal{C}}_{\rm{t}} , and a substitution scheduler s ; Output: the substituted circuit {\cal{C}}_{\rm{t}} ; 1 for i \gets |s|-1 to 0 do 2 Q_{\rm{m}} \gets qubits_mapping (s_i) ; 3 {\cal{C}}_{\rm{t}} \gets update (s_i, \, Q_{\rm{m}},\, {\cal{C}}_{\rm{t}}) ; 4 return {\cal{C}}_{\rm{t}}; Example 7. Continuing to consider Example 6, we take the replacement candidate ([{2,\ 13,\ 17}],\ r_3) as an example. We get the qubit mapping set Q_{\rm{m}} = \{f(q_0) = q_3,\ f(q_1) = q_{8}\} . The third gate of the target circuit {\cal{C}}_{\rm{t}} is updated by the gate ({ {“{\rm{c}}”}},\ q_3q_{8}) . The length of the pattern circuit is greater than that of the substitution circuit. Thus, the 13th and 17th gates are removed from the target circuit {\cal{C}}_{\rm{t}} .
5.3 Quantum Circuit Optimization
We develop a rule library for basic optimizations. The library is mainly used for basic reduction and quantum gate exchange[17, 33]. Note that almost all the gates implemented by quantum hardware devices are 1-qubit or 2-qubit gates, thus our rule library mainly concerns 1-qubit gates and 2-qubit gates. The maximum input scale involved in the rule set is up to 3-qubit gates. The gate specification involves some cancellation rules for 1-qubit gates and 2-qubit gates, as shown in Fig.5. The commutation rules shown in Fig.6 include transformation rules[33].
Sometimes, after a step of circuit rewriting the target circuit still matches some rules. We repeat several rounds of optimization and circuit rewriting until no pattern circuits can be matched or the specified repetition bound is reached (five by default in practice). It has been found experimentally that beyond five optimizations, the optimization opportunity decreases quickly. Hence, as a trade-off between optimization and running time, we choose to repeat the procedure five times.
6. Case Studies
In this section, we consider two examples: the first rewrites a circuit with three {\bf{CCZ}} gates to a circuit using the gate set G_{ {\rm{Sur}}} ; the second optimizes a circuit with a stochastic policy.
6.1 Rewriting a Circuit for Surface-17
We demonstrate QRewriting by rewriting the quantum circuit Toff-NC3[16] shown in Fig.7 to the gate set G_{ {\rm{Sur}}} [10] using the gate decomposition rules in Fig.8. The {\bf{CCZ}} gate decomposition rule[34] r = ( {\cal{C}}_{\rm{p}},\; {\cal{C}}_{\rm{s}}) is a pair, where
\begin{array}{l} {\cal{C}}_{\rm{p}} = ( { {“{\rm{E}}”}},\ q_0q_1q_2),\ \text{ and }\\ {\cal{C}}_{\rm{s}} = ( { {“{\rm{t}}”}},\ q_0)({ {“{\rm{t}}”}},\ q_1)({ {“{\rm{c}}”}},\ q_2q_0)({ {“{\rm{c}}”}},\ q_1q_2)\\ \;\;\;\;\;\;\;\;({ {“{\rm{T}}”}},\ q_0) ( { {“{\rm{T}}”}},\ q_2)({ {“{\rm{c}}”}},\ q_1q_0)({ {“{\rm{c}}”}},\ q_1q_2)({ {“{\rm{t}}”}},\ q_0)\\ \;\;\;\;\;\;\;\; ({ {“{\rm{c}}”}},\ q_2q_0) ( { {“{\rm{T}}”}},\ q_0)({ {“{\rm{t}}”}},\ q_2) ({ {“{\rm{c}}”}},\ q_1q_0). \end{array} The gate sequences of the target circuit and the decomposition pattern circuit are “{{\rm{hEhhEhhEh}}} ” and “{\rm{E}} ”, respectively. The subsequence set of {\cal{C}}_{\rm{t}} that can match “{\rm{E}} ” is \{[{1}],\ [{4}],\ [{7}]\} . Finally, the resulting circuit is shown in Fig.9.
6.2 Optimization with a Stochastic Policy
Next, we show an example of circuit optimization using QSRewriting with a stochastic policy. The target circuit and a set of rules {\cal{R}} = \{ r_0,\ r_1,\ r_2,\ r_3\} are shown in Fig.4(a) and Fig.1, respectively. The gate sequences of the target circuit and pattern circuits are “{{\rm{xxxxcccxxxxxcccxxxxcccxxxcccxxxxxxccc}}} ”, “ {\rm{xx}} ”, “ {\rm{cc}} ”, “{{\rm{ccc}}} ”, and “ {\rm{xcx}} ”, respectively. The subsequence sets of the gate sequence of the pattern circuits are as follows:
● “ {\rm{xx}} ”: \{[{3,\,9}],\,[{10,\,18}],\,[{0,\,22}],\,[{15,\,23}],\,[{16,\,24}]\},
● “ {\rm{cc}} ”: \{[{5,\ 12}],\ [{19,\ 25}]\},\
● “{\rm{ccc}} ”: \emptyset,
● “ {\rm{xcx}} ”: \{[{2,\ 13,\ 17}],\ [{18,\ 26,\ 31}]\}.
In Fig.4(a), we have marked the order of the elements in subsequence sets on the circuit symbols. The replacement candidates ([{10,\ 18}],\ r_0,\ 18) and ([{18,\ 26,\ 31}],\ r_3,\ 18) have a conflict at the index 18 of the target circuit. With the stochastic policy, either of the candidates can be chosen. Suppose the former is taken, then the generated replacement scheduler is given as follows:
\begin{array}{l} s = \{ ([{0,\ 22}],\ r_0),\ ([{2,\ 13,\ 17}],\ r_3),\ ([{3,\ 9}],\ r_0),\ \\ \ \ \;\; \;\; \;\;([{5,\ 12}],\ r_1),\ ([{10,\ 18}],\ r_0,\ 18),\ ([{15,\ 23}],\ r_0),\ \\ \ \ \;\; \;\; \;\;([{16,\ 24}],\ r_0),\ ([{19,\ 25}],\ r_1)\}. \end{array} Finally, we obtain the resulting circuit shown in Fig.4(b), which reduces the gate count and the depth by 49% and 20%, respectively.
7. Experiments
We compare QRewriting with a state-of-the-art algorithm for the quantum circuit optimization framework based on pattern matching, namely PaF[29]. Note that PaF is not freely available, and thus we implement it in Python. The implementation of QRewriting in Python is available online
4 . All the experiments are conducted on a Ubuntu machine with a 2.2 GHz CPU and 64 G memory. For the stochastic policy, we execute QSRewriting five times and take the average result; because other policies are deterministic, we execute them only once.We compare QSRewriting, QGRewriting, and PaF, using the BIGD[16] benchmarks and the rules shown in Fig.1, with the results shown in Fig.10. The depth and the gate count of the generated quantum circuits are used as evaluation metrics. The BIGD benchmarks are characterized by parameter (v_1,\ v_2) , which is called the gate density vector[16]. The two components stand for the densities of 1-qubit and 2-qubit gates of a circuit, respectively. Supposing a quantum circuit has n qubits, N_{\rm{1q}} (resp. N_{\rm{2q}} ) is the number of 1-qubit (resp. 2-qubit) gates, and the longest dependency chain is l , then v_1 = N_{\rm{1q}}/(n \times l) and v_2 = 2\times N_{\rm{2q}}/(n \times l) .
Figure 10. Comparison of the quantum circuits generated by QSRewriting, QGRewriting, and PaF optimized on the BIGD[16] benchmarks. (a) 1-qubit gate count. (b) 2-qubit gate count. (c) Total gate count. (d) Depth.The BIGD benchmarks include 360 circuits with a total of
129600 gates. After a PaF optimization, the gate count and the depth decrease by66236 and3999 within7125 seconds, respectively. QGRewriting (resp. QSRewriting) takes1387 (resp.1509 ) seconds to rewrite these benchmark circuits, and the generated circuits further reduce the 1-qubit gate count, 2-qubit gate count, total gate count, and depth by an average of 5.2% (resp. 4.5%), 57.0% (resp. 55.9%), 17.4% (resp. 16.7%), and 26.5% (resp. 24.8%), respectively, compared with PaF. The main evaluation results are shown in Fig.10, which compares the performance of QSRewriting, QGRewriting, and PaF in terms of 1-qubit gate count, 2-qubit gate count, total gate count, and depth of the generated circuits, respectively. The light blue bars represent the gate count (depth) of the benchmarks. The blue, red, and yellow lines represent PaF, QGRewriting, and QSRewriting, respectively. We can see that the red and yellow lines are mostly lower than the blue lines, and the yellow lines are mostly obscured by the red lines, but we can still see that the yellow lines are lower than the red ones in some places. In Fig.10(d), we can see that in a few cases, the depth of those quantum circuits might increase after optimizing. The reason is that the gates of a rear layer may be moved to the front layer, causing the original gates of the front layer to conflict with them.In Fig.10, QSRewriting is lower than QGRewriting on some BIGD benchmarks on which we compare the gate count and depth increments of the circuits generated by QSRewriting and QGRewriting, as shown in Fig.11(a) and Fig.11(b), respectively. In Fig.11, the light blue bars represent the total gate count (depth) of the circuits generated by QSRewriting and the blue parts are the increments in gate count (depth) that QGRewriting has over QSRewriting. The greedy policy is deterministic and the stochastic policy shows that better strategies exist. In Fig.12, we show a comparison of the time cost of the three methods optimized on the BIGD benchmarks, with PaF in blue, QGRewriting in red, and QSRewriting in yellow. It is clear that QGRewriting and QSRewriting use less time, as both the red and yellow lines are lower than the blue lines in Fig.12. On average, both QGRewriting and QSRewriting optimized on the BIGD benchmarks are about 5 times faster than PaF.
Figure 11. Comparison of the increments of the generated circuits on which QSRewriting outperforms QGRewriting both optimized on the BIGD[16] benchmarks. (a) Total gate count. (b) Depth.Figure 12. Comparison of the time cost for QSRewriting, QGRewriting, and PaF optimized on the BIGD[16] benchmarks.Now we consider rewriting a set of benchmark circuits[17] consisting of arithmetic circuits and implementations of multi-controlled Toffoli gates to the Surface-17 processor, as shown in Tables 3 and 4. The set of benchmark circuits uses the commonly used gate set G_{ {\rm{Com}}} (see Table 1) with a total of 33 circuits and
201554 gates. The gate set G_{ {\rm{Sur}}} supported by Surface-17 processor limits 1-qubit gates to {{\boldsymbol{R}}}_{\rm{x}} and {{\boldsymbol{R}}}_{\rm{y}} rotations and 2-qubit {\bf{CZ}} gate, and more specifically \pm{{{\pi}}}/{4} , \pm{{{\pi}}}/{2} , and \pm{{\pi}} degrees will be used in the decomposition, as shown in Fig.8. Thus, the rewriting of the benchmark circuits is from gate set G_{ {\rm{Com}}} to gate set G_{ {\rm{Sur}}} , and the gate count (resp. depth) and time cost for each phase are shown in Table 3 (resp. Table 4) in detail. Note that the rewriting of the benchmarks simply chooses the greedy policy since no replacement conflicts arise. We calculate the reduction rate of gate count (resp. depth) by optimizing each rewritten benchmark, as shown in the last column of Table 3 (resp. Table 4). The optimization of the rewritten circuits leads to a reduction of up to 52% in gate count and 49% in depth. However, there is a price to pay. For example, for the benchmark circuit “GF( 2^{163} )-Mult” in the last row of Table 3 with millions of gates, the rewriting without optimization takes about 15 minutes (see the last row of column t_1 ), while the rewriting with optimization may take about two hours (see the last row of column t_2 ), depending on the size of the rule library and the structure of the quantum circuit.Table 3. Comparison of Gate Count of Circuits Generated by QRewriting from the Benchmark Circuits[17]Benchmark n N N_0 t_0 N_1 t_1 N_2 t_2 \Delta(\%) Toff-NC3 5 9 45 0.00 135 0.03 80 0.50 40.74 Toff-Barenco3 5 10 58 0.00 174 0.07 101 0.52 41.95 Mod 54 5 15 63 0.00 187 0.09 89 0.57 52.41 Toff-NC4 7 15 75 0.00 225 0.10 134 0.89 40.44 Toff-Barenco4 7 18 114 0.00 342 0.19 198 1.12 42.11 Toff-NC5 9 21 105 0.00 315 0.18 188 1.34 40.32 Toff-Barenco5 9 26 170 0.01 510 0.32 296 1.70 41.96 VBE-Adder3 10 30 150 0.00 450 0.34 266 1.51 40.89 GF( 2^{4} )-Mult 12 33 225 0.01 675 0.58 388 2.68 42.52 Mod-Mult55 9 35 119 0.00 341 0.20 211 1.04 38.12 GF( 2^{5} )-Mult 15 47 347 0.01 1041 0.80 601 3.74 42.27 CSLA-MUX3 15 50 170 0.01 510 0.44 315 2.23 38.24 Toff-NC10 19 51 255 0.01 765 0.49 458 3.31 40.13 GF( 2^{6} )-Mult 18 63 495 0.02 1485 1.19 854 5.36 42.49 Toff-Barenco10 19 66 450 0.01 1350 0.95 786 4.76 41.78 RC-Adder6 14 68 200 0.01 584 0.93 361 2.66 38.18 Mod-Red21 11 74 278 0.01 786 0.93 463 3.39 41.09 GF( 2^{7} )-Mult 21 81 669 0.02 2007 1.61 1153 7.37 42.55 CSUM-MUX9 30 84 420 0.01 1204 1.57 721 3.98 40.12 QCLA-Com7 24 95 443 0.01 1299 1.02 778 5.98 40.11 QCLA-Adder10 36 113 521 0.01 1563 1.31 957 7.29 38.77 GF( 2^{8} )-Mult 24 115 883 0.02 2649 2.35 1516 12.95 42.77 GF( 2^{9} )-Mult 27 123 1095 0.03 3285 2.72 1885 12.09 42.62 GF( 2^{10} )-Mult 30 147 1347 0.03 4041 3.36 2316 14.90 42.69 QCLA-Mod7 26 176 884 0.02 2638 2.06 1570 12.24 40.49 Adder8 24 216 900 0.02 2676 6.79 1623 13.00 39.35 GF( 2^{16} )-Mult 48 363 3435 0.13 10305 9.44 5865 38.96 43.09 Mod-Adder 1024 28 865 4285 0.09 12855 18.19 7403 57.77 42.41 GF( 2^{32} )-Mult 96 1305 13593 0.30 40779 38.71 23069 157.25 43.43 GF( 2^{64} )-Mult 192 4539 53691 1.17 161073 146.63 91065 635.20 43.46 GF( 2^{128} )-Mult 384 17275 213883 5.59 641649 584.97 362429 3656.48 43.52 GF( 2^{131} )-Mult 393 18333 224265 5.90 672795 616.90 379766 3927.99 43.55 GF( 2^{163} )-Mult 489 27705 346533 9.67 1039599 945.51 587034 7452.82 43.53 Note: n : the number of qubits. N : the gate count of the circuit. N_0 : the gate count of the circuit after decomposition without optimization on gate set G_{ {\rm{Com}}} . N_1 : the gate count of the circuit after rewriting without optimization on gate set G_{ {\rm{Sur}}} . N_2 : the gate count of the circuit after rewriting with optimization on gate set G_{ {\rm{Sur}}} . t_i\, (i = 0,\ 1,\ 2) : running time in seconds. \Delta : (N_1-N_2)/N_1 \times 100\% . Table 4. Comparison of Depth of Circuits Generated by QRewriting from the Benchmark Circuits[17]Benchmark n d d_0 t_0 d_1 t_1 d_2 t_2 \Delta(\%) Toff-NC3 5 7 23 0.00 64 0.03 42 0.50 34.38 Toff-Barenco3 5 9 31 0.00 86 0.07 52 0.52 39.53 Mod 54 5 15 36 0.00 97 0.09 49 0.57 49.48 Toff-NC4 7 11 38 0.00 104 0.10 67 0.89 35.58 Toff-Barenco4 7 17 61 0.00 166 0.19 102 1.12 38.55 Toff-NC5 9 15 53 0.00 144 0.18 92 1.34 36.11 Toff-Barenco5 9 25 91 0.01 246 0.32 152 1.70 38.21 VBE-Adder3 10 20 70 0.00 194 0.34 113 1.51 41.75 GF( 2^{4} )-Mult 12 17 85 0.01 236 0.58 145 2.68 38.56 Mod-Mult55 9 14 43 0.00 118 0.20 80 1.04 32.20 GF( 2^{5} )-Mult 15 20 111 0.01 310 0.80 187 3.74 39.68 CSLA-MUX3 15 17 59 0.01 166 0.44 107 2.23 35.54 Toff-NC10 19 35 128 0.01 344 0.49 217 3.31 36.92 GF( 2^{6} )-Mult 18 25 139 0.02 384 1.19 235 5.36 38.80 Toff-Barenco10 19 65 241 0.01 646 0.95 402 4.76 37.77 RC-Adder6 14 28 93 0.01 261 0.93 166 2.66 36.40 Mod-Red21 11 43 141 0.01 383 0.93 238 3.39 37.86 GF( 2^{7} )-Mult 21 29 166 0.02 458 1.61 280 7.37 38.86 CSUM-MUX9 30 15 53 0.01 147 1.57 96 3.98 34.69 QCLA-Com7 24 15 70 0.01 192 1.02 115 5.98 40.10 QCLA-Adder10 36 15 64 0.01 182 1.31 111 7.29 39.01 GF( 2^{8} )-Mult 24 39 199 0.02 544 2.35 335 12.95 38.42 GF( 2^{9} )-Mult 27 36 219 0.03 606 2.72 367 12.09 39.44 GF( 2^{10} )-Mult 30 40 246 0.03 680 3.36 412 14.90 39.41 QCLA-Mod7 26 39 172 0.02 487 2.06 284 12.24 41.68 Adder8 24 55 191 0.02 527 6.79 315 13.00 40.23 GF( 2^{16} )-Mult 48 71 415 0.13 1136 9.44 699 38.96 38.47 Mod-Adder1024 28 521 2218 0.09 6397 18.19 3775 57.77 40.99 GF( 2^{32} )-Mult 96 137 849 0.30 2324 38.71 1447 157.25 37.74 GF( 2^{64} )-Mult 192 263 1711 1.17 4688 146.63 2856 635.20 39.08 GF( 2^{128} )-Mult 384 517 3437 5.59 9420 584.97 5750 3656.48 38.96 GF( 2^{131} )-Mult 393 537 3526 5.90 9658 616.90 5902 3927.99 38.89 GF( 2^{163} )-Mult 489 665 4390 9.67 12026 945.51 7310 7452.82 39.22 Note: n : the number of qubits. d : the depth of the circuit. d_0 : the depth of the circuit after decomposition without optimization on gate set G_{ {\rm{Com}}} . d_1 : the depth of the circuit after rewriting without optimization on gate set G_{ {\rm{Sur}}} . d_2 : the depth of the circuit after rewriting with optimization on gate set G_{ {\rm{Sur}}} . t_i\,\ (i = 0,\ 1,\ 2) : running time in seconds. \Delta : (d_1-d_2)/d_1\times 100\% . 8. Conclusions
We introduced a new representation of quantum circuits, which reduces the pattern matching of quantum circuits to the problem of finding distinct subsequences. We presented an algorithm based on dynamic programming to match the pattern circuits in the target circuit. To resolve replacement conflicts, we proposed three policies for generating a replacement scheduler and a polynomial-time replacement algorithm. We developed a rule library for basic optimizations and applied it to rewrite the benchmarks consisting of arithmetic circuits and implementations of multi-controlled Toffoli gates to the Surface-17 processor. Compared with the existing method PaF optimized on the BIGD benchmarks, QRewriting reduces the depth (resp. gate count) by 26.5% (resp. 17.4%), which demonstrates the effectiveness of the proposed method.
-
Figure 10. Comparison of the quantum circuits generated by QSRewriting, QGRewriting, and PaF optimized on the BIGD[16] benchmarks. (a) 1-qubit gate count. (b) 2-qubit gate count. (c) Total gate count. (d) Depth.
Figure 11. Comparison of the increments of the generated circuits on which QSRewriting outperforms QGRewriting both optimized on the BIGD[16] benchmarks. (a) Total gate count. (b) Depth.
Figure 12. Comparison of the time cost for QSRewriting, QGRewriting, and PaF optimized on the BIGD[16] benchmarks.
Table 1 Three Gate Sets for Different Scenarios
Gate Set Symbol G_{ {\rm{Com}}}[8] {\bf{H}}, {\bf{X}}, {\bf{Y}}, {\bf{Z}}, {\bf{S}}, {\bf{S}}^{\dagger}, {\bf{T}}, {\bf{T}}^{\dagger}, {\boldsymbol{R}}_{\rm z}(\theta), {\bf{CX }} G_{ {\rm{IBM}}}[9] {\boldsymbol{U }}_1(\theta), \ {\boldsymbol{U }}_2(\alpha,\ \lambda),\ {\boldsymbol{U }}_3(\theta,\ \alpha,\ \lambda), \ {\bf{CX }} G_{ {\rm{Sur}}}[10] {\bf{X}}, {\bf{Y}}, {\boldsymbol{R}}_{\rm{x}}(\theta), {\boldsymbol{R}}_{\rm{y}}(\theta), {\bf{CZ}} Table 2 Symbols of Gates and Distinct Aliases
Gate Aliase Circuit {\bf{I}} “I” {\bf{H}} “h” {\bf{X}} “x” {\bf{Y}} “y” {\bf{Z}} “z” {\bf{T}} “t” {\bf{T}}^{\dagger} “T” {\bf{S}} “s'' {\bf{S}}^{\dagger} “S” {{\boldsymbol{R}}}_{\rm{x}} “X' {{\boldsymbol{R}}}_{\rm{y}} “Y” {{\boldsymbol{R}}}_{\rm z} “Z” {\bf{CX }} “c” {\bf{CZ}} “C” {\bf{CCX}} “E” {\bf{CCZ}} “F” Table 3 Comparison of Gate Count of Circuits Generated by QRewriting from the Benchmark Circuits[17]
Benchmark n N N_0 t_0 N_1 t_1 N_2 t_2 \Delta(\%) Toff-NC3 5 9 45 0.00 135 0.03 80 0.50 40.74 Toff-Barenco3 5 10 58 0.00 174 0.07 101 0.52 41.95 Mod 54 5 15 63 0.00 187 0.09 89 0.57 52.41 Toff-NC4 7 15 75 0.00 225 0.10 134 0.89 40.44 Toff-Barenco4 7 18 114 0.00 342 0.19 198 1.12 42.11 Toff-NC5 9 21 105 0.00 315 0.18 188 1.34 40.32 Toff-Barenco5 9 26 170 0.01 510 0.32 296 1.70 41.96 VBE-Adder3 10 30 150 0.00 450 0.34 266 1.51 40.89 GF( 2^{4} )-Mult 12 33 225 0.01 675 0.58 388 2.68 42.52 Mod-Mult55 9 35 119 0.00 341 0.20 211 1.04 38.12 GF( 2^{5} )-Mult 15 47 347 0.01 1041 0.80 601 3.74 42.27 CSLA-MUX3 15 50 170 0.01 510 0.44 315 2.23 38.24 Toff-NC10 19 51 255 0.01 765 0.49 458 3.31 40.13 GF( 2^{6} )-Mult 18 63 495 0.02 1485 1.19 854 5.36 42.49 Toff-Barenco10 19 66 450 0.01 1350 0.95 786 4.76 41.78 RC-Adder6 14 68 200 0.01 584 0.93 361 2.66 38.18 Mod-Red21 11 74 278 0.01 786 0.93 463 3.39 41.09 GF( 2^{7} )-Mult 21 81 669 0.02 2007 1.61 1153 7.37 42.55 CSUM-MUX9 30 84 420 0.01 1204 1.57 721 3.98 40.12 QCLA-Com7 24 95 443 0.01 1299 1.02 778 5.98 40.11 QCLA-Adder10 36 113 521 0.01 1563 1.31 957 7.29 38.77 GF( 2^{8} )-Mult 24 115 883 0.02 2649 2.35 1516 12.95 42.77 GF( 2^{9} )-Mult 27 123 1095 0.03 3285 2.72 1885 12.09 42.62 GF( 2^{10} )-Mult 30 147 1347 0.03 4041 3.36 2316 14.90 42.69 QCLA-Mod7 26 176 884 0.02 2638 2.06 1570 12.24 40.49 Adder8 24 216 900 0.02 2676 6.79 1623 13.00 39.35 GF( 2^{16} )-Mult 48 363 3435 0.13 10305 9.44 5865 38.96 43.09 Mod-Adder 1024 28 865 4285 0.09 12855 18.19 7403 57.77 42.41 GF( 2^{32} )-Mult 96 1305 13593 0.30 40779 38.71 23069 157.25 43.43 GF( 2^{64} )-Mult 192 4539 53691 1.17 161073 146.63 91065 635.20 43.46 GF( 2^{128} )-Mult 384 17275 213883 5.59 641649 584.97 362429 3656.48 43.52 GF( 2^{131} )-Mult 393 18333 224265 5.90 672795 616.90 379766 3927.99 43.55 GF( 2^{163} )-Mult 489 27705 346533 9.67 1039599 945.51 587034 7452.82 43.53 Note: n : the number of qubits. N : the gate count of the circuit. N_0 : the gate count of the circuit after decomposition without optimization on gate set G_{ {\rm{Com}}} . N_1 : the gate count of the circuit after rewriting without optimization on gate set G_{ {\rm{Sur}}} . N_2 : the gate count of the circuit after rewriting with optimization on gate set G_{ {\rm{Sur}}} . t_i\, (i = 0,\ 1,\ 2) : running time in seconds. \Delta : (N_1-N_2)/N_1 \times 100\% . Table 4 Comparison of Depth of Circuits Generated by QRewriting from the Benchmark Circuits[17]
Benchmark n d d_0 t_0 d_1 t_1 d_2 t_2 \Delta(\%) Toff-NC3 5 7 23 0.00 64 0.03 42 0.50 34.38 Toff-Barenco3 5 9 31 0.00 86 0.07 52 0.52 39.53 Mod 54 5 15 36 0.00 97 0.09 49 0.57 49.48 Toff-NC4 7 11 38 0.00 104 0.10 67 0.89 35.58 Toff-Barenco4 7 17 61 0.00 166 0.19 102 1.12 38.55 Toff-NC5 9 15 53 0.00 144 0.18 92 1.34 36.11 Toff-Barenco5 9 25 91 0.01 246 0.32 152 1.70 38.21 VBE-Adder3 10 20 70 0.00 194 0.34 113 1.51 41.75 GF( 2^{4} )-Mult 12 17 85 0.01 236 0.58 145 2.68 38.56 Mod-Mult55 9 14 43 0.00 118 0.20 80 1.04 32.20 GF( 2^{5} )-Mult 15 20 111 0.01 310 0.80 187 3.74 39.68 CSLA-MUX3 15 17 59 0.01 166 0.44 107 2.23 35.54 Toff-NC10 19 35 128 0.01 344 0.49 217 3.31 36.92 GF( 2^{6} )-Mult 18 25 139 0.02 384 1.19 235 5.36 38.80 Toff-Barenco10 19 65 241 0.01 646 0.95 402 4.76 37.77 RC-Adder6 14 28 93 0.01 261 0.93 166 2.66 36.40 Mod-Red21 11 43 141 0.01 383 0.93 238 3.39 37.86 GF( 2^{7} )-Mult 21 29 166 0.02 458 1.61 280 7.37 38.86 CSUM-MUX9 30 15 53 0.01 147 1.57 96 3.98 34.69 QCLA-Com7 24 15 70 0.01 192 1.02 115 5.98 40.10 QCLA-Adder10 36 15 64 0.01 182 1.31 111 7.29 39.01 GF( 2^{8} )-Mult 24 39 199 0.02 544 2.35 335 12.95 38.42 GF( 2^{9} )-Mult 27 36 219 0.03 606 2.72 367 12.09 39.44 GF( 2^{10} )-Mult 30 40 246 0.03 680 3.36 412 14.90 39.41 QCLA-Mod7 26 39 172 0.02 487 2.06 284 12.24 41.68 Adder8 24 55 191 0.02 527 6.79 315 13.00 40.23 GF( 2^{16} )-Mult 48 71 415 0.13 1136 9.44 699 38.96 38.47 Mod-Adder1024 28 521 2218 0.09 6397 18.19 3775 57.77 40.99 GF( 2^{32} )-Mult 96 137 849 0.30 2324 38.71 1447 157.25 37.74 GF( 2^{64} )-Mult 192 263 1711 1.17 4688 146.63 2856 635.20 39.08 GF( 2^{128} )-Mult 384 517 3437 5.59 9420 584.97 5750 3656.48 38.96 GF( 2^{131} )-Mult 393 537 3526 5.90 9658 616.90 5902 3927.99 38.89 GF( 2^{163} )-Mult 489 665 4390 9.67 12026 945.51 7310 7452.82 39.22 Note: n : the number of qubits. d : the depth of the circuit. d_0 : the depth of the circuit after decomposition without optimization on gate set G_{ {\rm{Com}}} . d_1 : the depth of the circuit after rewriting without optimization on gate set G_{ {\rm{Sur}}} . d_2 : the depth of the circuit after rewriting with optimization on gate set G_{ {\rm{Sur}}} . t_i\,\ (i = 0,\ 1,\ 2) : running time in seconds. \Delta : (d_1-d_2)/d_1\times 100\% . -
[1] Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proc. the 35th Annual Symposium on Foundations of Computer Science, Nov. 1994, pp.124–134. DOI: 10.1109/SFCS.1994.365700.
[2] Grover L K. A fast quantum mechanical algorithm for database search. In Proc. the 28th Annual ACM Symposium on Theory of Computing, May 1996, pp.212–219. DOI: 10.1145/237814.237866.
[3] Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Physical Review Letters, 2009, 103(15): 150502. DOI: 10.1103/PhysRevLett.103.150502.
[4] Arute F, Arya K, Babbush R et al. Quantum supremacy using a programmable superconducting processor. Nature, 2019, 574(7779): 505–510. DOI: 10.1038/s41586-019-1666-5.
[5] Madsen L S, Laudenbach F, Askarani M F et al. Quantum computational advantage with a programmable photonic processor. Nature, 2022, 606(7912): 75–81. DOI: 10.1038/s41586-022-04725-x.
[6] Preskill J. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: Article No. 79. DOI: 10.22331/q-2018-08-06-79.
[7] Kjaergaard M, Schwartz M E, Braumüller J, Krantz P, Wang J I J, Gustavsson S, Oliver W D. Superconducting qubits: Current state of play. Annual Review of Condensed Matter Physics, 2020, 11(1): 369–395. DOI: 10.1146/annurev-conmatphys-031119-050605.
[8] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information (10th Anniversary Eedition). Cambridge: Cambridge University Press, 2010.
[9] Murali P, Linke N M, Martonosi M, Abhari A J, Nguyen N H, Alderete C H. Full-stack, real-system quantum computer studies: Architectural comparisons and design insights. In Proc. the 46th ACM/IEEE International Symposium on Computer Architecture, Jun. 2019, pp.527–540. DOI: 10.1145/3307650.3322273.
[10] Lao L, van Someren H, Ashraf I, Almudéver C G. Timing and resource-aware mapping of quantum circuits to superconducting processors. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(2): 359–371. DOI: 10.1109/TCAD.2021.3057583.
[11] Siraichi M Y, dos Santos V F, Collange S, Pereira F M Q. Qubit allocation. In Proc. the 2018 International Symposium on Code Generation and Optimization, Feb. 2018, pp.113–125. DOI: 10.1145/3168822.
[12] Li G, Ding Y, Xie Y. Tackling the qubit mapping problem for NISQ-era quantum devices. In Proc. the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, Apr. 2019, pp.1001–1014. DOI: 10.1145/3297858.3304023.
[13] Liu L, Dou X. QuCloud: A new qubit mapping mechanism for multi-programming quantum computing in cloud environment. In Proc. the IEEE International Symposium on High-Performance Computer Architecture (HPCA), Feb. 27–Mar. 3, 2021, pp.167–178. DOI: 10.1109/HPCA51647.2021.00024.
[14] Liu L, Dou X. QuCloud+: A holistic qubit mapping scheme for single/multi-programming on 2D/3D NISQ quantum computers. ACM Trans. Architecture and Code Optimization, 2024, 21(1): Article No. 9. DOI: 10.1145/3631525.
[15] Childs A M, Schoute E, Unsal C M. Circuit transformations for quantum architectures. In Proc. the 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), May 2019, Article No. 3. DOI: 10.4230/LIPIcs.TQC.2019.3.
[16] Tan B, Cong J. Optimality study of existing quantum computing layout synthesis tools. IEEE Trans. Computers, 2021, 70(9): 1363–1373. DOI: 10.1109/TC.2020.3009140.
[17] Nam Y, Ross N J, Su Y, Childs A M, Maslov D. Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information, 2018, 4: Article No. 23. DOI: 10.1038/s41534-018-0072-4.
[18] Sivarajah S, Dilkes S, Cowtan A, Simmons W, Edgington A, Duncan R. t|ket⟩: A retargetable compiler for NISQ devices. Quantum Science and Technology, 2021, 6(1): 014003. DOI: 10.1088/2058-9565/ab8e92.
[19] Jia Z, Padon O, Thomas J, Warszawski T, Zaharia M, Aiken A. TASO: Optimizing deep learning computation with automatic generation of graph substitutions. In Proc. the 27th ACM Symposium on Operating Systems Principles, Oct. 2019, pp.47–62. DOI: 10.1145/3341301.3359630.
[20] Kissinger A, Wetering J. PyZX: Large scale automated diagrammatic reasoning. In Proc. the 16th International Conference on Quantum Physics and Logic, Jun. 2019, pp.229–241.
[21] Pointing J, Padon O, Jia Z H, Ma H, Hirth A, Palsberg J, Aiken A. Quanto: Optimizing quantum circuits with automatic generation of circuit identities. Quantum Science and Technology, 2024, 9(4): 045009.
[22] Xu M, Li Z, Padon O, Lin S, Pointing J, Hirth A, Ma H, Palsberg J, Aiken A, Acar U A, Jia Z. Quartz: Superoptimization of quantum circuits. In Proc. the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Jun. 2022, pp.625–640. DOI: 10.1145/3519939.3523433.
[23] McKeeman W M. Peephole optimization. Communications of the ACM, 1965, 8(7): 443–444. DOI: 10.1145/364995.365000.
[24] Abdessaied N, Soeken M, Wille R, Drechsler R. Exact template matching using Boolean satisfiability. In Proc. the 43rd IEEE International Symposium on Multiple-Valued Logic, May 2013, pp.328–333. DOI: 10.1109/ISMVL.2013.26.
[25] Iten R, Moyard R, Metger T, Sutter D, Woerner S. Exact and practical pattern matching for quantum circuit optimization. ACM Trans. Quantum Computing, 2022, 3(1): Article No. 4. DOI: 10.1145/3498325.
[26] Rahman M M, Dueck G W. Optimal quantum circuits of three qubits. In Proc. the 42nd IEEE International Symposium on Multiple-Valued Logic, May 2012, pp.161–166. DOI: 10.1109/ISMVL.2012.43.
[27] Prasad A K, Shende V V, Markov I L, Hayes J P, Patel K N. Data structures and algorithms for simplifying reversible circuits. ACM Journal on Emerging Technologies in Computing Systems, 2006, 2(4): 277–293. DOI: 10.1145/1216396.1216399.
[28] Soeken M, Dueck G W, Rahman M M, Miller D M. An extension of transformation-based reversible and quantum circuit synthesis. In Proc. the 2016 IEEE International Symposium on Circuits and Systems (ISCAS), May 2016, pp.2290–2293. DOI: 10.1109/ISCAS.2016.7539041.
[29] Chen M, Zhang Y, Li Y. A quantum circuit optimization framework based on pattern matching. SPIN, 2021, 11(3): 2140008. DOI: 10.1142/S2010324721400087.
[30] Wagner R A, Fischer M J. The string-to-string correction problem. Journal of the ACM, 1974, 21(1): 168–173. DOI: 10.1145/321796.321811.
[31] Bellman R. Dynamic programming. Science, 1966, 153(3731): 34–37. DOI: 10.1126/science.153.3731.34.
[32] Zhang Y, Deng H, Li Q, Song H, Nie L. Optimizing quantum programs against decoherence: Delaying qubits into quantum superposition. In Proc. the 2019 International Symposium on Theoretical Aspects of Software Engineering, Jul. 2019, pp.184–191. DOI: 10.1109/TASE.2019.000-2.
[33] Iwama K, Kambayashi Y, Yamashita S. Transformation rules for designing CNOT-based quantum circuits. In Proc. the 39th Annual Design Automation Conference, Jun. 2002, pp.419–424. DOI: 10.1145/513918.514026.
[34] Amy M, Azimzadeh P, Mosca M. On the controlled-NOT complexity of controlled-NOT–phase circuits. Quantum Science and Technology, 2018, 4(1): Article No. 015002. DOI: 10.1088/2058-9565/aad8ca.
-
期刊类型引用(1)
1. Hui Jiang, Jianling Fu, Yuxin Deng, et al. A binary integer programming-based method for qubit mapping in sparse architectures. Acta Informatica, 2025, 62(1) 必应学术
其他类型引用(0)
-
其他相关附件
-
本文附件外链
https://rdcu.be/d6X8C -
DOCX格式
2726-Chinese-Information 点击下载(35KB) -
PDF格式
2024-6-7-2726-Highlights 点击下载(196KB)
-