Penggandaan matriks kuantum?

Sepertinya ini tidak diketahui - tetapi apakah ada batas bawah yang menarik pada kompleksitas perkalian matriks dalam model komputasi kuantum? Apakah kita memiliki intuisi yang dapat mengalahkan kompleksitas algoritma Coppersmith-Winograd menggunakan komputer kuantum?

reference-request quantum-computing matrix-product Henry Yuen
sumber

Jawaban:

Dalam arXiv: quant-ph / 0409035v2 Buhrman dan Spalek menyajikan algoritma kuantum mengalahkan algoritma Coppersmith-Winograd dalam kasus di mana matriks output memiliki beberapa entri bukan-nol.

Pembaruan: Ada juga algoritma kuantum yang sedikit ditingkatkan oleh Dörn dan Thierauf .

Pembaruan: Ada peningkatan algoritma kuantum oleh Le Gall mengalahkan Burhman dan Spalek secara umum.

Martin Schwarz
sumber

Ini baru bagi saya (saya tahu sedikit tentang hasil kuantum), tetapi melirik kertas, hasilnya bahkan lebih mengejutkan! Jika, untuk perkalian matriks

, ada

A_{n x m} B_{m x n} = C_{n x n}

$A_{nxm}B_{mxn}=C_{nxn}$

entri bukan-nol dalam output, produk dapat dihitung dalam waktusub-kuadrat,

o (\sqrt{n})

$o(\sqrt{n})$

o (n m)

$o(nm)$

Daniel Apon

Ada sedikit perbaikan untuk ini untuk kasus khusus dari produk matriks Boolean, min {

} ketika ada

nonzeroes dalam output. (Itu muncul di makalah FOCS'10 kami `` Kesamaan Subkubis Antara Masalah Jalur, Matriks, dan Segitiga ''.)

n^{1.3} w^{17 / 30}, n^{2} + w^{47 / 60} n^{13 / 15}

$n^{1.3}w^{17/30}, n^2 + w^{47/60} n^{13/15}$

w

$w$

virgi

n w^{1 / 2}

$nw^{1/2}$

$v^\dagger X Y v$ $v X^{-1} v$ $X$

Joe Fitzsimons
sumber

v^{'} X Y v

$v'XYv$

@ Aram: Poin bagus! Saya tahu algoritma Anda berfungsi untuk matriks jarang, tetapi saya mendapat kesan bahwa itu bisa dibuat untuk matriks tertentu juga. Apakah ini benar?

Joe Fitzsimons

Ya, itu berfungsi untuk matriks non-jarang setiap kali kita tahu cara yang baik untuk mensimulasikan orang-orang Hamilton. Jadi mungkin sesuatu nontrivial mungkin terjadi di sini.

Aram Harrow

@ Aram: Dengan pengkodean yang Anda gunakan, bukankah kita juga mendapatkan transformasi Fourier dari semua matriks jarang melalui QFT?

Joe Fitzsimons

@ Jo: Aku baru memperhatikan ini. Ya, matriks-matriks itu (yang dapat Anda anggap jarang dalam basis momentum) juga dapat digunakan. Ini tidak ada yang unik dari algoritma kami. Alih-alih itu adalah pernyataan tentang kelas orang Hamilton yang kita tahu cara mensimulasikan komputer kuantum.

Aram Harrow