Optimization of Oracle circuits based on minimum weight and template matching

YANG Donghan; LI Zhiqiang; WU Xi; PAN Wenjie; YANG Hui

doi:10.3969/j.issn.1007-5461.2024.01.015

Journals >Chinese Journal of Quantum Electronics >Volume 41 >Issue 1 >Page 151 > Article

Chinese Journal of Quantum Electronics
Vol. 41, Issue 1, 151 (2024)

Optimization of Oracle circuits based on minimum weight and template matching

YANG Donghan, LI Zhiqiang^*, WU Xi, PAN Wenjie, and YANG Hui

Author Affiliations

College of Information Engineering, Yangzhou University, Yangzhou 225100, China

show less

DOI: 10.3969/j.issn.1007-5461.2024.01.015 Cite this Article

Donghan YANG, Zhiqiang LI, Xi WU, Wenjie PAN, Hui YANG. Optimization of Oracle circuits based on minimum weight and template matching[J]. Chinese Journal of Quantum Electronics, 2024, 41(1): 151 Copy Citation Text

show less

Fig. 1. Deutsch circuit

Download full size | View in the Article

Fig. 2. Grover circuit

Download full size | View in the Article

Fig. 3. Oracle circuit

f (0,2, 6,7) = 1

Download full size | View in the Article

Fig. 4. Oracle circuit

f (4,6) = 1

Download full size | View in the Article

Fig. 5. Derivation process of R3

Download full size | View in the Article

Fig. 6. Examples of R1-R3. (a) R1; (b) R2; (c) R3

Download full size | View in the Article

Fig. 7. (a) Initial circuit of

f (3,4, 7,9, 11,12,13,14) = 1

; (b) Gate matching of algorithm 2; (c) Circuit conversion of algorithm 1；(d) Final circuit

Download full size | View in the Article

Fig. 8. Derivation process of template 1

Download full size | View in the Article

Fig. 9. Derivation process of template 2

Download full size | View in the Article

Fig. 10. Matching process of template. (a) T2 matching; (b) T1 matching; (c) T2 matching; (d) Final circuit

Download full size | View in the Article

算法4 Oracle整体优化算法

输入:MCT门集合gates

输出:优化后的线路gates

1. do{

2. g1←Optimize(gates) //阶段1优化

3. g2←T1_Match (g1) //阶段2模板T1优化

4. gates←T2_Match (g2) //阶段2模板T2优化

5. }while(gates != g1)

6. return gates

Table 0. [in Chinese]

算法3 基于最小权匹配的线路替换算法Optimize

输入: MCT门集合gates

输出: 等效变换后的门集合gates1

1. gates1←new hash() // 初始化输出的门集合

2. for key in gates{ // key表示MCT门的控制线位置信息

3. n←gates[key].length // 具有相同控制线的MCT门集合, 有n个元素

4. Match(gates[key]) // 算法2重排序, 实现最小权匹配

5. for i←0 to n/2 do{ // 共有n/2个门对

6. gates1.add(Merge(key, gates[key][i*2], gates[key][i*2+1]))}} // 算法1两两替换

7. if n % 2 = 1{ // n为奇数, 最后一个门直接存储

8. gates1.add(gates[key][n-1]) }

9. if gates1 = gates{ // 不再替换生成新的线路

10. return gates1 } // 返回结果线路

11. Optimize (gates1) // 在新的线路中递归算法3

Table 0. [in Chinese]

算法2 门集合的最小权匹配算法 Match

输入: 相同控制线位置的门集合gates, 门集合构成图G

输出: 配对后的门集合retGates

1. retGates←Ø // 初始化输出门集合

2. while gates = Ø{

3. for each G(i) ∈G do{ // 提取边权为i 的子图, 即MCT门互补控制点数目为i

4. gates'←Blossom(G(i )) // 利用开花算法找到互补控制点为i的最大匹配

5. retGates.add(gates' ) // 添加到结果

6. gates←gates – gates' }} // 去除已匹配的点

7. return retGates

Table 0. [in Chinese]

算法1 线路转换算法Merge

输入:key , value1, value2

输出:等效线路gates

1. gates←ϕ // 定义输出线路gates

2. count←value1⊕value2 //确定控制点不同的位置(位运算)

3. while (count){

4. lastIndex←count & (-count) //获取最低位的1(位运算)

5. key←Set the log(lastIndex)-th 1 of the key to 0 // 得到新的控制线位置

6. gates[key].add(((value1 >> 1) & ~(lastIndex - 1)) + ((lastIndex - 1) & value1))

7. count←count & (count-1) } //最低位的1清0, 迭代次数减1

8. return gates

Table 0. [in Chinese]

	$f (x)$	Original		RCViewer⁺		Phase1		Phase2		Impr/%
	$f (x)$	GC	QC	GC	QC	GC	QC	GC	QC	GC	QC
1	{0, 1, 3, 4, 5, 9, 12, 15}	8	232	8	108	5	42	5	33	37.5	69.4
2	{0, 1, 7, 10, 11, 12, 14, 15}	8	232	8	106	6	45	5	38	37.5	64.2
3	{0, 2, 3, 6, 9, 10, 11, 14}	8	232	7	93	5	36	3	25	57.1	73.1
4	{1, 2, 5, 7, 8, 11, 12, 15}	8	232	7	91	4	26	4	16	42.9	82.4
5	{1, 3, 8, 11, 12, 13, 14, 15}	8	232	6	78	5	65	3	39	50.0	50.0
6	{2, 3, 4, 5, 10, 11, 12, 14}	8	232	4	52	4	38	4	28	0.0	46.2
7	{2, 5, 6, 7, 8, 10, 12, 13}	8	232	8	232	5	43	4	34	50.0	85.3
8	{3, 4, 7, 9, 11, 12, 13, 14}	8	232	11	143	5	49	4	40	63.6	72.0
9	{4, 5, 6, 7, 9, 11, 12, 14}	8	232	4	52	3	11	2	6	50.0	88.5
10	{4, 7, 8, 9, 10, 11, 12, 15}	8	232	6	78	4	19	3	15	50.0	80.8
	Avg			6.9	103.3			3.7	27.4	46.4	73.5

Table 1. Deutsch optimized experimental results with n = 4

$n$	Original		RCViewer⁺		Phase1		Phase2		Impr/%		ET/s
$n$	GC	QC	GC	QC	GC	QC	GC	QC	GC	QC	ET/s
4	8	232	7	86	4	39	4	32	42.9	62.8	<0.1
5	16	976	13	396	10	151	7	115	46.2	71.0	0.1
6	32	4000	29	1555	22	471	15	342	48.3	78.0	0.3
7	64	16192	60	4840	48	1428	30	993	50.0	79.5	1.4
8	128	65152	122	12204	106	3619	59	2379	51.6	80.5	9.2
9	256	261376	245	31413	226	9578	123	6328	49.8	79.9	87.2
10	512	1047040	496	147448	475	109340	265	60153	46.6	59.2	741.3
Avg			138.9	28277.4			71.9	10048.9	48.3	64.5

Table 2. Optimized experimental results of DJ’s Oracle circuit with n bit

$n$	Original		RCViewer⁺		Phase1		Phase2		Impr/%		ET/s
$n$	GC	QC	GC	QC	GC	QC	GC	QC	GC	QC	ET/s
4	3	88	2	36	2	36	2	34	0.0	5.6	<0.1
5	5	301	4	114	4	112	4	108	0.0	5.3	<0.1
6	8	1122	7	343	8	330	7	308	0.0	10.2	0.1
7	17	4351	17	939	17	921	15	831	11.8	11.5	0.4
8	31	15809	36	2306	35	2233	29	1984	19.4	14.0	1.2
9	58	59994	87	6307	83	6126	67	5200	23.0	17.6	8.3
10	134	266443	235	15937	219	15507	167	12798	28.9	19.7	123.9
Avg			55.4	3711.7			41.6	3037.6	25.0	18.2

Table 3. Optimized experimental results of Grover’s Oracle circuitwith n bit

Donghan YANG, Zhiqiang LI, Xi WU, Wenjie PAN, Hui YANG. Optimization of Oracle circuits based on minimum weight and template matching[J]. Chinese Journal of Quantum Electronics, 2024, 41(1): 151

Download Citation

Tools

Save the article for my favorites

Paper Information

微信扫一扫：分享

微信扫一扫：分享