Kompilasi otomatis dari sirkuit kuantum

12

Sebuah pertanyaan baru-baru ini di sini bertanya bagaimana mengkompilasi gerbang 4-qubit CCCZ (dikendalikan-dikendalikan-dikendalikan-Z) menjadi gerbang 1-qubit dan 2-qubit yang sederhana, dan satu-satunya jawaban yang diberikan sejauh ini membutuhkan 63 gerbang !

Langkah pertama adalah menggunakan konstruksi C U yang diberikan oleh Nielsen & Chuang:n

Dengan ini berarti 4 gerbang CCNOT dan 3 gerbang sederhana (1 CNOT dan 2 Hadamard cukup untuk melakukan CZ akhir pada target qubit dan qubit pekerjaan terakhir).n=3

Teorema 1 dari makalah ini , mengatakan bahwa secara umum CCNOT membutuhkan 9 gerbang satu-qubit dan 6 gerbang dua-qubit (15 total):

masukkan deskripsi gambar di sini


Ini berarti:

(4 CCNOT) x (15 gerbang per CCNOT) + (1 CNOT) + (2 Hadamard) = 63 total gerbang .

Dalam sebuah komentar , telah disarankan bahwa 63 gerbang kemudian dapat dikompilasi lebih lanjut menggunakan "prosedur otomatis", misalnya dari teori kelompok otomatis .

Bagaimana "kompilasi otomatis" ini dapat dilakukan, dan berapa banyak yang akan mengurangi jumlah gerbang 1-qubit dan 2-qubit dalam kasus ini?

pengguna1271772
sumber
1
Saya ada di tengah-tengah beberapa hal tetapi melihat pertanyaan Anda. Gerbang Global Mølmer – Sørensen adalah 2 gerbang qubit, dan makalah Penggunaan interaksi global dalam konstruksi sirkuit kuantum yang efisien menggambarkan: "Implementasi optimal gerbang CCCZ menggunakan tiga gerbang GMS", lihat gambar 9. Anda dipersilakan untuk menulis jawaban jika itu bermanfaat.
Rob
Representasi dalam gambar hanya membutuhkan 4 CCNOT, dan karenanya 63 gerbang, bukan 93.
Dyon J Don Kiwi van Vreumingen
@ DonKiwi, perhatikan! 4 CCNOT bukannya 6. Saya memperbarui sekarang.
user1271772
1
@Rob: Sepertinya Anda menyarankan untuk mengkonjugasikan X di CCCX menggunakan dua Hadamard. Kemudian CCCX dapat diurai seperti di sirkuit Nielsen & Chaung di atas. Apakah itu benar? Dalam jawaban kedua saya untuk pertanyaan DonKiwi, saya melakukan sesuatu seperti ini. Sepertinya komentar Anda datang tepat ketika saya mengetik jawaban itu, karena mereka terpisah 5 menit (dan butuh lebih dari 5 menit bagi saya untuk mengetiknya). Pertanyaan tentang "kompilasi otomatis" ini tetap ada, karena akan lebih baik untuk dapat membangun sirkuit dengan "cara yang jelas" dan kemudian secara otomatis mengkompilasi menjadi sesuatu yang lebih efisien.
user1271772
1
@ user1271772 - Setiap (qu) bit membantu.
Rob

Jawaban:

6

Biarkan menjadi gerbang dasar yang diizinkan untuk Anda gunakan. Untuk keperluan ini dan dll diperlakukan sebagai terpisah. Jadi secara polinomi tergantung pada , jumlah qubit. Ketergantungan yang tepat melibatkan rincian macam gerbang Anda gunakan dan bagaimana -local mereka. Misalnya, jika ada gerbang qubit tunggal dan gerbang -qubit yang tidak bergantung pada pesanan seperti maka .g1gMCNOT12CNOT13MnkxyCZM=xn+(n2)y

Sirkuit kemudian merupakan produk dari generator tersebut dalam beberapa urutan. Tetapi ada beberapa sirkuit yang tidak melakukan apa-apa. Seperti . Jadi itu memberi hubungan pada kelompok. Itu adalah presentasi grup mana ada banyak hubungan yang tidak kita ketahui.CNOT12CNOT12=Id g1gMR1

Masalah yang ingin kita selesaikan diberikan kata dalam grup ini, apa kata terpendek yang mewakili elemen yang sama. Untuk presentasi kelompok umum, ini tidak ada harapan. Jenis presentasi kelompok di mana masalah ini dapat diakses disebut otomatis.

Tetapi kita dapat mempertimbangkan masalah yang lebih sederhana. Jika kita membuang beberapa , maka kata-kata dari sebelum menjadi bentuk mana masing-masing adalah kata-kata hanya dalam huruf yang tersisa. Jika kami berhasil membuatnya lebih pendek menggunakan relasi yang tidak melibatkan , maka kami akan membuat seluruh rangkaian lebih pendek. Ini mirip dengan mengoptimalkan CNOT sendiri yang dibuat di jawaban lain.giw1gi1w2gi2wkwigi

Misalnya, jika ada tiga generator dan kata tersebut adalah , tetapi kami tidak ingin berurusan dengan , sebaliknya kami akan mempersingkat dan menjadi dan . Kami kemudian menyatukannya kembali sebagai dan itu adalah kependekan dari kata aslinya.aababbacbbabacw1=aababbaw2=bbabaw^1w^2w^1cw^2

Jadi WLOG (tanpa kehilangan umum), misalkan kita sudah berada dalam masalah itu mana kita sekarang menggunakan semua gerbang yang ditentukan. Sekali lagi ini mungkin bukan grup otomatis. Tetapi bagaimana jika kita membuang beberapa hubungan. Kemudian kita akan memiliki grup lain yang memiliki peta hasil bagi ke yang kita inginkan.g1gMR1

Grup tidak ada relasi yang merupakan grup gratis , tetapi jika Anda menempatkan sebagai relasi, Anda mendapatkan produk gratis dan ada peta hasil bagi dari yang sebelumnya ke yang kemudian mengurangi jumlah di setiap segmen modulo .g1g2g12=id Z2Zg12

Relasi yang kita buang akan sedemikian rupa sehingga yang lantai atas (sumber peta hasil bagi) akan otomatis dengan desain. Jika kita hanya menggunakan relasi yang tersisa dan mempersingkat kata, maka itu akan tetap menjadi kata yang lebih pendek untuk grup hasil bagi. Itu tidak akan optimal untuk grup hasil bagi (target peta hasil bagi), tetapi ia akan memiliki panjang dengan panjangnya dimulai.

Itu adalah ide umum, bagaimana kita bisa mengubahnya menjadi algoritma tertentu?

Bagaimana kita memilih dan relasi yang akan dibuang untuk mendapatkan grup otomatis? Di sinilah pengetahuan tentang jenis gerbang dasar yang biasanya kita gunakan masuk. Ada banyak keterlibatan, jadi pertahankan hanya itu. Berhati-hatilah dengan fakta bahwa ini hanya involusi elementer, jadi jika perangkat keras Anda kesulitan menukar qubit yang jauh terpisah pada chip Anda, ini hanya menuliskannya dalam bentuk yang dapat Anda lakukan dengan mudah dan mengurangi kata itu menjadi sesingkat mungkin.gi

Misalnya, anggap Anda memiliki konfigurasi IBM . Kemudian adalah gerbang yang diizinkan. Jika Anda ingin melakukan permutasi umum, dekomposisikan menjadi . Itu adalah kata dalam grup yang ingin kami perpendek .s01,s02,s12,s23,s24,s34si,i+1s01,s02,s12,s23,s24,s34R1

Perhatikan bahwa ini tidak harus menjadi involusi standar. Anda dapat memasukkan selain misalnya. Pikirkan teorema Gottesman-Knill , tetapi secara abstrak itu artinya akan lebih mudah untuk digeneralisasi. Seperti menggunakan properti yang di bawah urutan tepat pendek, jika Anda memiliki sistem penulisan ulang lengkap yang terbatas untuk kedua belah pihak, maka Anda mendapatkan satu untuk grup tengah. Komentar itu tidak perlu untuk sisa jawaban, tetapi menunjukkan bagaimana Anda dapat membangun contoh yang lebih umum lebih besar dari yang ada di jawaban ini.R(θ)XR(θ)1X

Relasi yang disimpan hanyalah . Ini memberikan grup Coxeter dan otomatis. Bahkan, kita bahkan tidak harus mulai dari awal untuk menyusun algoritma untuk struktur otomatis ini. Ini sudah diimplementasikan dalam Sage (berbasis Python) secara umum. Yang harus Anda lakukan adalah menentukan dan implementasi yang tersisa sudah dilakukan. Anda mungkin melakukan beberapa speedup di atas itu.(gigj)mij=1mij

mij benar-benar mudah dihitung karena sifat lokalitas dari gerbang. Jika gerbang paling banyak lokal, maka perhitungan dapat dilakukan pada ruang Hilbert dimensi . Ini karena jika indeks tidak tumpang tindih, maka Anda tahu bahwa . untuk saat dan bepergian. Anda juga hanya perlu menghitung kurang dari setengah entri. Ini karena matriks simetris, memiliki pada diagonal ( ). Juga sebagian besar entri hanya mengganti nama qubit yang terlibat jadi jika Anda tahu urutannyakmij22k1mij=2mij=2gigjmij1(gigi)1=1(CNOT12H1) , Anda tahu urutan tanpa melakukan perhitungan lagi.CNOT37H3

Itu mengurus semua hubungan yang hanya melibatkan paling banyak dua gerbang yang berbeda (bukti: latihan). Hubungan yang melibatkan atau lebih semuanya dibuang. Kita sekarang menempatkan mereka kembali. Katakanlah kita memilikinya, maka kita dapat melakukan algoritma serakah Dehn menggunakan hubungan baru. Jika ada perubahan, kita ketuk kembali untuk menjalankan melalui grup Coxeter lagi. Ini berulang sampai tidak ada perubahan.3

Setiap kali kata tersebut semakin pendek atau tetap sama dan kami hanya menggunakan algoritma yang memiliki perilaku linier atau kuadratik. Ini adalah prosedur yang agak murah jadi sebaiknya lakukan dan pastikan Anda tidak melakukan hal bodoh.

Jika Anda ingin mengujinya sendiri, berikan jumlah generator sebagai , panjang dari kata acak yang Anda coba dan matriks Coxeter sebagai .NKm

edge_list=[]
for i1 in range(N):
    for j1 in range(i):
        edge_list.append((j1+1,i1+1,m[i1,j1]))
G3 = Graph(edge_list)
W3 = CoxeterGroup(G3)
s3 = W3.simple_reflections()
word=[choice(list([1,..,N])) for k in range(K)]
print(word)
wTesting=s3[word[0]]
for o in word[1:]:
    wTesting=wTesting*s3[o]
word=wTesting.coset_representative([]).reduced_word()
print(word)

Contoh dengan N=28dan K=20, dua baris pertama adalah input kata yang tidak direduksi, dua baris berikutnya adalah kata yang dikurangi. Saya harap saya tidak membuat kesalahan ketik saat memasukkan matriks .m

[26, 10, 13, 16, 15, 16, 20, 22, 21, 25, 11, 22, 25, 13, 8, 20, 19, 19, 14, 28]

['CNOT_23', 'Y_1', 'Y_4', 'Z_2', 'Z_1', 'Z_2', 'H_1', 'H_3', 'H_2', 'CNOT_12', 'Y_2', 'H_3', 'CNOT_12', 'Y_4', 'X_4', 'H_1', 'Z_5', 'Z_5', 'Y_5', 'CNOT_45']

[14, 8, 28, 26, 21, 10, 15, 20, 25, 11, 25, 20]

['Y_5', 'X_4', 'CNOT_45', 'CNOT_23', 'H_2', 'Y_1', 'Z_1', 'H_1', 'CNOT_12', 'Y_2', 'CNOT_12', 'H_1']

Menempatkan kembali generator seperti kami hanya mengembalikan hubungan seperti dan itu - dengan gerbang yang tidak melibatkan qubit . Hal ini memungkinkan kami untuk membuat dekomposisi dari sebelum memiliki selama mungkin. Kami ingin menghindari situasi seperti . (Dalam Cliff + T orang sering berusaha untuk meminimalkan T-count). Untuk bagian ini, grafik asiklik langsung yang menunjukkan ketergantungan sangat penting. Ini adalah masalah menemukan jenis DAG topologi yang baik. Itu dilakukan dengan mengubah prioritas ketika seseorang memiliki pilihan titik apa yang akan digunakan berikutnya. (Saya tidak akan membuang waktu untuk mengoptimalkan bagian ini terlalu keras.)TiTin=1Tiiw1gi1w2gi2wkwiX1T2X1T2X1T2X1

Jika kata sudah mendekati panjang optimal, tidak banyak yang bisa dilakukan dan prosedur ini tidak akan membantu. Tetapi sebagai contoh paling mendasar dari apa yang ditemukannya adalah jika Anda memiliki banyak unit dan Anda lupa ada di akhir satu dan di awal berikutnya, itu akan menyingkirkan pasangan itu. Ini berarti Anda dapat black box rutinitas umum dengan keyakinan yang lebih besar bahwa ketika Anda menyatukannya, pembatalan yang jelas itu semua akan diurus. Itu orang lain yang tidak jelas; yang digunakan saat .HiHimij1,2

Lagi pula
sumber
+1 !!! Banyak detail! Saya membacanya :)
user1271772
1
@ Wahussain, mungkinkah mengerjakan contoh di mana ini diterapkan pada konstruksi CCCZ "naif" dalam pertanyaan saya, dan berakhir dengan jumlah gerbang yang lebih kecil? Pertanyaan awal tentang CCCZ sekarang memiliki 6 jawaban, dan banyak dari mereka memiliki jumlah gerbang yang jauh lebih kecil. Saya ingin tahu apa pendekatan Anda akan memberi untuk menghitung gerbang.
user1271772
4

Dengan menggunakan prosedur yang diuraikan dalam https://arxiv.org/abs/quant-ph/0303063 1 , setiap gerbang diagonal - apa pun yang secara khusus gerbang CCCZ - dapat didekomposisi dalam hal misalnya CNOT dan gerbang diagonal satu-qubit, di mana CNOT dapat dioptimalkan sendiri mengikuti prosedur optimasi klasik.

Referensi menyediakan sirkuit menggunakan 16 CNOT untuk gerbang 4-qubit diagonal yang sewenang-wenang (Gbr. 4).


Catatan: Walaupun pada prinsipnya mungkin ada rangkaian yang lebih sederhana (rangkaian kata tersebut telah dioptimalkan dengan arsitektur sirkuit yang lebih terbatas dalam pikiran), sirkuit itu harus mendekati optimal - rangkaian perlu membuat semua keadaan dalam bentuk untuk setiap subset non-sepele , dan ada 15 dari mereka untuk 4 qubit.iIxiI{1,2,3,4}

Perhatikan juga bahwa konstruksi ini tidak perlu optimal.


1 Catatan: Saya seorang penulis

Norbert Schuch
sumber
Menarik. Saya masih harus membaca koran untuk melihat prosedurnya. Saya juga menunggu @AHussain untuk memberi tahu kami bagaimana melakukannya menggunakan teori grup otomatis.
user1271772