Size optimization of CNOT circuits on NISQ

2025-05-03 0 0 463.04KB 12 页 10玖币

侵权投诉

Anpeng Zhang, Xiutao Feng and Shengyuan Xu

Academy of Mathmatics and Systems Science Chinese Academy of Science, Beijing, China,

{zhanganpeng,fengxt,xushengyuan18}@amss.ac.cn

Abstract.

Quantum computers in practice today require strict memory constraints,

where 2-qubit operations can only be performed between the qubits closest to each

other in a graph structure. So a quantum circuit must undergo a transformation to

the graph before it can be implemented. In this paper, we study the optimization

of the CNOT circuits on some noisy intermediate-scale quantum(NISQ) devices.

Compared with previous works, we decompose it into two sub-problems: optimization

with a given initial qubit distribution and optimization without limitations of initial

qubit distribution. We ﬁnd that most of the previous researches focused on the

ﬁrst sub-problem, and ignored the inﬂuence of diﬀerent distribution of qubits in the

same topology structure on the optimization results. In this paper, We take both

sub-problems into account and give some new optimization algorithms. In short, our

method is divided into two steps: matrix optimization and routing optimization. We

implement matrix optimization with the algorithm in [XZL

20] and put forward a

new heuristic algorithm with MILP method which can solve the second step. We

implement our algorithm on IBM20 and some other NISQ devices, the results are

better than most other methods in our experiment.

Keywords:

CNOT circuits

topologically-constrained

graph structure

MILP

NISQ

1 Introduction

With the rapid development of quantum computing technology, quantum computer has

gradually become a reality. Now noisy intermediate-scale quantum (NISQ) [Pre18] comput-

ers with 10-80 qubits have been made by some laboratories such as IBM and Google [Nay19].

In current quantum computers, many physical implementations of quantum computers

such as superconducting quantum circuits [Nay19] [ROT

18] and ion traps [BSK

12]

[BHL

16] impose strict memory limits, where 2-qubit operations (such as CNOT gates)

can only be performed between the nearest qubits in a lattice or graphical structure. For

a given quantum circuit with no limitation of memory operation, how to transform it into

a circuit that can be realized on a real quantum computer has become an urgent problem

to be solved. The traditional solution to this problem is to exchange qubits through the

SWAP gate operation between adjacent qubits to achieve the realization of two quantum

gates between two non-adjacent qubits [ZPW18] [HS18]. However, this scheme is too costly,

which usually increases the depth of the circuit and the number of gates by 1.5 to 3 times.

In fact, ﬁnding the exact optimal solution appears intractable [HND17].

In 2019, Kissinger

et al

[KdG19] showed that a pure CNOT circuit can be compiled

directly on an NISQ without signiﬁcantly increasing the number of CNOT gates. Inspired

by classic SLP problem, they transformed a CNOT circuit (linear map) into a matrix and

then performed Restricted Gauss elimination to ﬁnd its optimal implementation under the

limit of some topological graphs. Later Nash

et al

proposed a similar algorithm which can

implement any CNOT circuit with a 4

-size equivalent CNOT circuit on any connected

arXiv:2210.05184v1 [quant-ph] 11 Oct 2022

2 Size optimization of CNOT circuits on NISQ

graph [NGM20]. In 2021, Xiaoming Sun

et al

put forward a new algorithm wihch gives a

-size equivalent CNOT circuit for any CNOT circuit on any connected graph

and

proved that the lower bound of this problem is

(

n2/logδ

), where

denotes the maximum

degree of vertices in G[WHY+19].

It has shown that ﬁnding the minimum CNOT gates in implementation for a CNOT

circuit without restriction can correspond to a Shortest Linear Program (SLP) problem,

and the latter was proved to be an NP-hard problem [BMP13]. In 2020, Xiang Zejun

et al

presented a new heuristic algorithm to search the optimal implementations of reasonable

large matrices based on the s-Xor operation [XZL

20]. Their basic idea is to ﬁnd various

matrix decompositions for a given matrix and optimize those decompositions to get the

best implementation. In order to optimize matrix decompositions, they present several

matrix multiplication rules over

, which are proved to be very powerful in reducing the

implementation cost.

In this paper we mainly discuss the optimization of the CNOT circuit under some

topologically-constrained quantum memories. First we abstract it into a concrete mathe-

matical problem, and give a new heuristic algorithm. Our algorithm includes two steps:

1) ﬁnd the optimal implementation of the corresponding matrix of the CNOT circuit by

Xiang et al’s method;

2) optimize the qubit distribution according to the result of Step 1) by means of the solver

Gurobi.

For consistency, we use the same set of randomly-generated CNOT circuits on 9, 16, and

20 qubits, and list the results in Table 1. The speciﬁc algorithm and implementation can

be found on Github. It is seen that our results are better than the QuilC [SCZ16],

t|keti

compilers [CDD+19] and stenier tree [KdG19] in most cases.

The paper is organized as follows. We start in Section 2 by reviewing some basic

knowledge of quantum computing. In Section 3, we abstract the optimization of CNOT

circuit into mathematical problems and detail our method, including matrix optimization

and distribution optimization of qubits. In Section 4, we compared our experimental

results with previous works and apply our method in the quantum implementation of

AES’s Mixcolumns.

2 Preliminaries

2.1 CNOT circuit

Classical computer circuits consist of wires and logic gates [NC02]. The wires are used to

carry information around the circuit, while the logic gates perform manipulations of the

information, converting it from one form to another. For example, the logic gate Xor can

transform bits

and

a⊕b

, where

a, b

= 0

1. But diﬀerent from classical bit, the

qubit is in superposition:

|ψi=α|0i+β|1i

And we can write it in a vector notation as

|ψi=α

β

In order to realize XOR operation on quantum computers, we introduce a multi-qubit

gate, which is called the controlled-NOT or CNOT gate. This gate has two input qubits,

known as the control qubit and the target qubit, respectively.

Another way of describing the action of the CNOT gate is to give a matrix representation.

In fact, every qubit gate can correspond to a unitary matrix, we use

UCN

to denote the

Anpeng Zhang, Xiutao Feng and Shengyuan Xu 3

|Ai•|Ai

|Bi |A⊕Bi

Figure 1: Controlled-NOT gate

CNOT gate.

UCN =





1000

0100

0001

0010







One can easily check that

U†

CN UCN

. Of course, there are many interesting quantum

gates other than the controlled-NOT. But here we only focus on quantum circuit which is

composed of CNOT gates.

Deﬁnition 1

: A quantum circuit is called a CNOT circuit if it contains only CNOT gates.

Figure 2:

An example of CNOT circuit swapping two qubits, and an equivalent schematic

symbol notation

In fact, since the CNOT circuit is linear, it is easy to map it to an

n×n

matrix over

(2), and each CNOT gate can correspond to an elementary row operation of a matrix,

such as CNOTi,j is actually adding the row iof the matrix to the row j.

2.2 CNOT basis transformations

In some practical quantum computers such as IBM-QX5 in ﬁgure 3, there is a strict limit

between the control bit and the target bit, and the target bit cannot be used as the control

bit for controlled operation, but if we only consider CNOT circuits, we can ignore the

limitations by the follow fact.

Figure 3: a quantum circuit interchanging controlled bit and target bit of a CNOT gate

Thus, with four hamdamard gates, we implement the interchange of a controlled bit and a

target bit. All graphs we will mention in the rest of this paper are undirected graphs.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

SizeoptimizationofCNOTcircuitsonNISQAnpengZhang,XiutaoFengandShengyuanXuAcademyofMathmaticsandSystemsScienceChineseAcademyofScience,Beijing,China,{zhanganpeng,fengxt,xushengyuan18}@amss.ac.cnAbstract.Quantumcomputersinpracticetodayrequirestrictmemoryconstraints,where2-qubitoperationscanonlybeperform...

展开>> 收起<<

Size optimization of CNOT circuits on NISQ.pdf

共12页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Size optimization of CNOT circuits on NISQ

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: