Klasik doğrusal cebir çözücüler, benzer hızlanmalarla kuantum algoritmalarını uygulayabilir mi?
Bir kuantum algoritması, bir başlangıç durumunda bir kübit kaydı ile başlar, üniter bir operatör (algoritma) bu kübitlerin durumunu yönetir ve ardından kübitlerin durumu okunur (veya en azından tek bir algoritmanın çalıştırılması).
Bana öyle geliyor ki bir kuantum bilgisayar, kuantum durum üzerindeki üniter eylemler sorusuna yanıt veriyor. Bu "sadece" bir doğrusal cebir meselesidir. O halde, kuantum bilgisayarların doğrusal cebir hesaplayıcıları olarak görülebilmesi beni şaşırtıyor.
O halde neden kuantum mekaniğine ihtiyacımız var? Doğrusal cebir işlemlerini uygulayan klasik bir sistem bulup bunu kuantum bilgisayarlar için tasarlanmış algoritmaları uygulamak için kullanamaz mıyız? Elbette klasik dijital bilgisayarlar yeterli olmayacaktır, bu makineler yüksek boyutlu bir uzayda vektörlerin manipülasyonundan ziyade ikili bilgi işlemeye dayanmaktadır.
Soru: Klasik doğrusal cebir çözücüler (klasik analog bilgisayarlar) için dijital klasik bilgisayarlara göre benzer bir hızlanmanın tadını çıkarırken "kuantum bilgisayar" algoritmalarını uygulayabilecek herhangi bir aday var mı?
Soru 2: Belki de bir kuantum bilgisayarı basitçe bir doğrusal cebir çözücüsü haline getirerek fazla basitleştiriyorum. Durum bu mu? Hangi karmaşıklığın üzerinden geçiyorum?
Yanıtlar
Gözden geçirdiğiniz karmaşıklık, genel durumda saklamanız gerekmesidir. $2^n$ bile temsil edecek karmaşık genlikler $n$Klasik olarak kübit sistemi. Bu nedenle, diyelim ki 1000 kübitlik bir kuantum bilgisayar için saklamanız gerekir$2^{1000}$karmaşık genlikler. Bunu yapmak için genlik başına bir atom kullansanız bile, gözlemlenebilir evrende hala atomlarınız biter.
Bildiğim kadarıyla, yukarıdaki genel argümandır. Bununla birlikte, algoritmanın temsili ihtiyaçlarından tasarruf etmek için bazı zekice içgörülerden yararlanarak belirli kuantum algoritmalarını klasik olarak izlenebilir bir şekilde temsil etmenin yolları olabilir, böylece$2^n$gereksinim. Ancak bu muhtemelen probleme özgüdür ve genel durumda işe yaraması olası değildir.
Sayısal ve analog hesaplama ile ilgili sorunun ifadesine göre, bu sitede benzer teklifleri sorgulayan başka konular da var. Örneğin, buraya ve buraya bakın . Diğer şeylerin yanı sıra, klasik analog sistemler birbirine karışamaz; dolayısıyla bir kuantum bilgisayarın analog bir bilgisayar olarak yeniden kullanılması, aynı gözlemlenen hızlanmaya yol açmayacaktır.
Bununla birlikte, @Attila Kun'un cevabına ek olarak, doğrusal cebir / makine öğreniminde hızlı kuantum algoritmalarına sahip olan ancak benzer hızlara sahip klasik algoritmalar olarak yeniden biçimlendirilen belirli problemler vardır.
Örneğin, Netflix / Amazon / vb. Tarafından kullanılan öneri sorunu . kuantum bilgisayarda hızlı bir algoritmaya sahiptir. Bu algoritma, (o zamanlar) en iyi bilinen klasik algoritmaya göre üssel gelişme gösterdi.
Bununla birlikte, kuantum algoritmasının gerçekten üstün olduğunu kanıtlamaya çalışırken, E. Tang gerçekten de "doğrusal cebir işlemlerini uygulayan ve bunu kuantum bilgisayarlar için tasarlanmış algoritmaları uygulamak için kullanan klasik bir sistem" olduğunu gösterdi.
Tang'ın çalışması, bir dekantizasyon programını başlattı - yani doğrusal cebir / makine öğreniminde hızlı kuantum algoritmalarını hızlı klasik algoritmalar olarak yeniden tasarlama. Bir Quanta Magazine makalesi sorunu ve Tang'ın yaklaşımını anlatıyor.
Bu dekuantizasyonu olarak, aktif bir araştırma alanıdır için problemler müsait Hangi Konuyu tartışıyor. Bu, dikkate alınan matrislerin derecesine bağlı olabilir.