Quantum Computing - Hubungan antara model Hamiltonian dan Unitary

16

Ketika mengembangkan algoritma dalam komputasi kuantum, saya perhatikan bahwa ada dua model utama di mana ini dilakukan. Beberapa algoritma - seperti untuk masalah pohon Hamiltonian NAND (Farhi, Goldstone, Guttman) - pekerjaan dengan merancang Hamiltonian dan beberapa keadaan awal, dan kemudian membiarkan berevolusi sistem menurut persamaan Schrödinger untuk beberapa waktu sebelum melakukan pengukuran.t

Algoritma lain - seperti Algoritma Shor untuk anjak piutang - bekerja dengan merancang sekuens transformasi Unitary (analog dengan gerbang) dan menerapkan transformasi ini satu per satu ke beberapa kondisi awal sebelum melakukan pengukuran.

Pertanyaan saya adalah, sebagai pemula dalam komputasi kuantum, apa hubungan antara model Hamilton dan model transformasi Unitary? Beberapa algoritma, seperti untuk masalah pohon NAND, sejak itu telah diadaptasi untuk bekerja dengan urutan transformasi Kesatuan (Childs, Cleve, Jordan, Yonge-Mallo). Bisakah setiap algoritma dalam satu model ditransformasikan menjadi algoritma yang sesuai di yang lain? Misalnya, diberi urutan transformasi Unitary untuk menyelesaikan masalah tertentu, apakah mungkin untuk merancang Hamiltonian dan menyelesaikan masalah dalam model itu? Bagaimana dengan arah lainnya? Jika demikian, apa hubungan antara waktu di mana sistem harus berkembang dan jumlah transformasi kesatuan (gerbang) yang diperlukan untuk menyelesaikan masalah?

Saya telah menemukan beberapa masalah lain yang kelihatannya seperti ini, tetapi tidak ada argumen atau bukti yang jelas yang akan menunjukkan bahwa ini selalu mungkin atau bahkan benar. Mungkin itu karena saya tidak tahu apa masalah ini, jadi saya tidak yakin apa yang harus dicari.

algorithms quantum-computing computation-models pengguna340082710
sumber
3
Setiap algoritma waktu polinomial dalam satu sesuai dengan algoritma waktu polinomial di yang lain, tetapi tidak jelas tingkat polinomial akan sama. Semoga seseorang akan datang dengan referensi. Hasil ini dibuktikan pada hari-hari awal perhitungan kuantum, dan seharusnya ada bukti yang lebih baik dari teorema ini sekarang.
Peter Shor
Apakah ini berhubungan dengan apa yang dikenal sebagai gambar QM Heisenberg vs Schroedinger yang berhubungan dengan bagaimana operator didefinisikan? juga jika tidak tercakup dalam Nielsen & Chuang maka itu tampaknya akan menjadi pengawasan utama! kertas pohon NAND menggunakan "nubuat hamiltonian" yang tampaknya diperkenalkan oleh Farhi / Gutmann 1998. di sini adalah artikel survei yang bagus tentang nubuat Hamiltonian oleh Mochon 2007
vzn
Tautan buku yang Anda berikan sebenarnya adalah buku teks yang kami gunakan dalam kursus sarjana saya di Pemrosesan Informasi Quantum. Buku ini benar-benar diarahkan pada pendekatan Kesatuan (dalam konteks nubuat juga), tetapi tidak begitu banyak dalam konteks orang Hamilton. Program sarjana saya difokuskan dari perspektif cs dan bukan dari perspektif fisika, itulah sebabnya saya paling akrab dengan model Unitary.
user340082710
Makalah yang Anda berikan juga merupakan referensi yang bagus secara umum, tapi saya juga tidak yakin itu menjawab pertanyaan saya. Terakhir, saya telah melihat gambar QM Heisenberg vs Schroedinger, dan memang terlihat terkait, tetapi saya percaya pertanyaan saya berbeda (meskipun saya bisa salah - Sulit untuk mengikuti entri Wikipedia).
user340082710
Saya pikir ada berbagai cara untuk menafsirkan pertanyaan Anda dan alih-alih menjawab semua penafsiran, saya ingin bertanya kepada Anda yang berikut: Bisakah Anda lebih tepat tentang versi model Hamilton yang ada dalam pikiran Anda? Apa ukuran kompleksitas dalam model ini? (yaitu, apa yang menghitung seberapa sulitnya untuk menyelesaikan masalah dalam model Hamiltonian?) Bagaimana input untuk masalah yang diberikan? Apakah itu diberikan secara eksplisit atau Anda harus meminta input melalui oracle?
Robin Kothari

Jawaban:

10

Untuk menunjukkan bahwa evolusi Hamilton dapat mensimulasikan model rangkaian, seseorang dapat menggunakan perhitungan Universal paper dengan multi-particle walk , yang menunjukkan bahwa jenis evolusi Hamiltonian yang sangat spesifik (multi-particle walks quantum) adalah BQP lengkap, dan dengan demikian dapat mensimulasikan model rangkaian.

Berikut ini adalah makalah survei tentang simulasi evolusi kuantum pada komputer kuantum. Orang dapat menggunakan teknik dalam makalah ini untuk mensimulasikan model evolusi Hamiltonian komputer kuantum. Untuk melakukan ini, kita perlu menggunakan "Trotterisasi", yang secara substansial mengurangi efisiensi simulasi (walaupun itu hanya menimbulkan ledakan polinomial dalam waktu perhitungan).

Peter Shor
sumber
Terima kasih! Referensi ini terlihat cukup baik dan seharusnya dapat memberi saya gambaran tentang bagaimana hal ini dilakukan.
user340082710