Bagaimana algoritma Grover digunakan untuk memperkirakan rata-rata dan median dari serangkaian angka?

Pada halaman Wikipedia untuk algoritma Grover , disebutkan bahwa:

"Algoritma Grover juga dapat digunakan untuk memperkirakan rata-rata dan median dari sekumpulan angka"

Sejauh ini saya hanya tahu bagaimana bisa digunakan untuk mencari basis data. Tetapi tidak yakin bagaimana menerapkan teknik itu untuk memperkirakan rata-rata dan median dari serangkaian angka. Selain itu, tidak ada kutipan (sejauh yang saya perhatikan) pada halaman itu yang menjelaskan tekniknya.

algorithm grovers-algorithm Sanchayan Dutta
sumber

Entah jika Anda memilih untuk menjawab pertanyaan Anda sendiri, atau untuk siapa lagi memilih mengambil tugas untuk diri mereka sendiri, link ini terlihat seperti tempat yang bagus untuk memulai Bagaimana Algoritma Gunakan Grover untuk menemukan rata-rata (alias Mean, Integral) dari Fungsi Weirdo

agaitaarino

@agaitaarino Terima kasih. Saya akan memeriksanya. Omong-omong, komentar Anda tidak dirender dengan benar sebagai tautan karena Anda meninggalkan ruang kosong setelah tanda kurung buka. :)

Sanchayan Dutta

Saya pikir makalah yang relevan adalah "Algoritma kuantum yang optimal untuk memperkirakan rata-rata dan aplikasinya untuk mendekati median dari satu set poin pada jarak acak" oleh Brassard et al .

Craig Gidney

Gagasan untuk memperkirakan rata-rata kira-kira sebagai berikut:

Untuk setiap yang memberikan output dalam real, tentukan diperbesar ulang yang memberikan output dalam kisaran 0 hingga 1. Kami bertujuan untuk memperkirakan rata-rata . $f(x)$ $F(x)$ $F(x)$
Tentukan kesatuan yang operasi adalah $U_a$ Penting untuk dicatat bahwa kesatuan ini mudah diimplementasikan. Anda mulai dengan transformasi Hadamard pada register pertama, lakukan perhitunganpada register ancilla, gunakan ini untuk menerapkan rotasi terkontrol register kedua, dan kemudian hitung komputasi register ancilla.
$U_{a} : | 0 ⟩ | 0 ⟩ \mapsto \frac{1}{2^{n / 2}} \sum_{x} | x ⟩ (\sqrt{1 - F (x)} | 0 ⟩ + \sqrt{F (x)} | 1 ⟩) .$ $U_a:|0\rangle|0\rangle\mapsto\frac{1}{2^{n/2}}\sum_x|x\rangle(\sqrt{1-F(x)}|0\rangle+\sqrt{F(x)}|1\rangle).$ $f(x)$
Mendefinisikan kesatuan . $G=U_a (\mathbb{I}-2|0\rangle\langle 0|\otimes |0\rangle\langle 0|)U_a^\dagger \mathbb{I}\otimes Z$
Mulai dari keadaan , menggunakan banyak seperti Anda akan menggunakan Grover iterator untuk memperkirakan jumlah solusi untuk masalah pencarian. $U_a|0\rangle|0\rangle$ $G$

| ψ ⟩ = \frac{1}{\sqrt{\sum_{x} F (x)}} \sum_{x} \sqrt{F (x)} | x ⟩ | 1 ⟩ | ψ^{⊥} ⟩ = \frac{1}{\sqrt{\sum_{x} 1 - F (x)}} \sum_{x} \sqrt{1 - F (x)} | x ⟩ | 0 ⟩,

$|\psi\rangle=\frac{1}{\sqrt{\sum_x F(x)}}\sum_x\sqrt{F(x)}|x\rangle|1\rangle \qquad |\psi^\perp\rangle=\frac{1}{\sqrt{\sum_x 1-F(x)}}\sum_x\sqrt{1-F(x)}|x\rangle|0\rangle,$

U_{a} | 0 ⟩ | 0 ⟩ = (\sqrt{\sum_{x} F (x)} | ψ ⟩ + \sqrt{\sum_{x} 1 - F (x)} | ψ^{⊥} ⟩) 2^{- n / 2}

$U_a|0\rangle|0\rangle=(\sqrt{\sum_x F(x)}|\psi\rangle+\sqrt{\sum_x 1-F(x)}|\psi^\perp\rangle)2^{-n/2}$

| ψ ⟩

$|\psi\rangle$

F (x)

$F(x)$

| 1 ⟩

$|1\rangle$

| ψ ⟩

$|\psi\rangle$

I \otimes Z

$\mathbb{I}\otimes Z$

\sqrt{\frac{m}{2^{n}}}

$\sqrt{\frac{m}{2^n}}$

m

$m$

$U_a$ $\frac{\mathbb{I}}{2^n}\otimes|0\rangle\langle 0|$

$z$

\sum_{x} | f (x) - f (z) | .

$\sum_x|f(x)-f(z)|.$

T

$T$

x

$x$

f (x) \leq T

$f(x)\leq T$

T

$T$

Tentu saja, saya melewatkan beberapa detail waktu berjalan yang tepat, perkiraan kesalahan dll.

DaftWullie
sumber

Apakah Anda harus terlebih dahulu menjalankan algoritme Grover beberapa kali logaritmik untuk menghitung nilai min dan maks fungsi sebelum Anda dapat melakukan penyetelan ulang pada langkah 1?

tparker

@parker Itu mungkin tergantung. Seringkali diasumsikan bahwa Anda cukup tahu tentang fungsi F untuk dapat mengikat nilai-nilai yang mungkin.

DaftWullie

Bagaimana algoritma Grover digunakan untuk memperkirakan rata-rata dan median dari serangkaian angka?

Jawaban: