Kuantum algoritması - Quantum algorithm

Olarak kuantum bilgisayar , bir kuantum algoritması bir bir algoritma gerçek bir modeli üzerinde çalışan kuantum bilgisayar en yaygın olarak kullanılan model olan, kuantum devre hesaplama modeli. Klasik (veya kuantum olmayan) bir algoritma, her adımın veya talimatın klasik bir bilgisayarda gerçekleştirilebildiği, sonlu bir talimat dizisi veya bir problemi çözmek için adım adım bir prosedürdür . Benzer şekilde, bir kuantum algoritması, adımların her birinin bir kuantum bilgisayarda gerçekleştirilebildiği adım adım bir prosedürdür . Tüm klasik algoritmalar bir kuantum bilgisayarda da gerçekleştirilebilse de, kuantum algoritması terimi genellikle, doğası gereği kuantum gibi görünen veya kuantum süperpozisyonu veya kuantum dolaşıklığı gibi kuantum hesaplamanın bazı temel özelliklerini kullanan algoritmalar için kullanılır .

Klasik bilgisayarlar kullanılarak çözülemeyen problemler, kuantum bilgisayarlar kullanılarak çözülemez kalır. Kuantum algoritmalarını ilginç kılan şey, bazı problemleri klasik algoritmalardan daha hızlı çözebilmeleridir, çünkü kuantum algoritmalarının yararlandığı kuantum süperpozisyonu ve kuantum dolaşıklığı muhtemelen klasik bilgisayarlarda verimli bir şekilde simüle edilemez (bkz. Kuantum üstünlüğü ).

En iyi bilinen algoritmalar, Shor'un faktoring algoritması ve Grover'ın yapılandırılmamış bir veritabanı veya sırasız bir listeyi aramaya yönelik algoritmasıdır . Shor'un algoritmaları, faktoring için en iyi bilinen klasik algoritma olan genel sayı alanı eleklerinden çok (neredeyse üstel olarak) daha hızlı çalışır . Grover'ın algoritması, aynı görev için mümkün olan en iyi klasik algoritma olan doğrusal bir aramadan ikinci dereceden daha hızlı çalışır .

genel bakış

Kuantum algoritmaları, genellikle, kuantum hesaplamanın yaygın olarak kullanılan devre modelinde , bazı girdi kübitlerine etki eden ve bir ölçüm ile sona eren bir kuantum devresi ile tanımlanır . Bir kuantum devresi , en fazla sabit sayıda kübit üzerinde hareket eden basit kuantum kapılarından oluşur . Kübitlerin sayısı sabitlenmelidir çünkü değişen sayıda kübit, üniter olmayan evrim anlamına gelir. Kuantum algoritmaları, Hamiltonian oracle modeli gibi diğer kuantum hesaplama modellerinde de belirtilebilir .

Kuantum algoritmaları, algoritma tarafından kullanılan ana tekniklere göre kategorize edilebilir. Kuantum algoritmalarında yaygın olarak kullanılan bazı teknikler/fikirler , faz geri tepmesi , faz tahmini , kuantum Fourier dönüşümü , kuantum yürüyüşleri , genlik büyütme ve topolojik kuantum alan teorisini içerir . Kuantum algoritmaları, çözülen problemin türüne göre de gruplandırılabilir, örneğin cebirsel problemler için kuantum algoritmaları anketine bakın.

Kuantum Fourier dönüşümüne dayalı algoritmalar

Fourier dönüşümü kuantum kuantum analogudur ayrık Fourier dönüşümü , ve çeşitli kuantum algoritmalar kullanılır. Hadamard dönüşüm Fourier alanı üzerinden bir n-boyutlu vektör alan üzerinde bir dönüşüm kuantum örneğidir F 2 . Kuantum Fourier dönüşümü, yalnızca bir polinom sayıda kuantum kapısı kullanılarak bir kuantum bilgisayarda verimli bir şekilde uygulanabilir .

Deutsch-Jozsa algoritması

Deutsch-Jozsa algoritması

Deutsch-Jozsa algoritması , herhangi bir deterministik klasik bilgisayar için muhtemelen kara kutuya katlanarak çok sayıda sorgu gerektiren bir kara kutu problemini çözer , ancak bir kuantum bilgisayar tarafından tam olarak bir sorgu ile yapılabilir. Hem sınırlı-hatalı kuantum hem de klasik algoritmalara izin verirsek, klasik bir olasılık algoritması sorunu sabit sayıda sorgu ile küçük hata olasılığı ile çözebildiğinden hızlanma olmaz. Algoritma, bir f fonksiyonunun sabit (tüm girişlerde 0 veya tüm girişlerde 1) veya dengeli (giriş alanının yarısı için 1 ve diğer yarısı için 0 döndürür) olup olmadığını belirler .

Bernstein-Vazirani algoritması

Bernstein-Vazirani algoritması, bir problemi en iyi bilinen klasik algoritmadan daha verimli çözen ilk kuantum algoritmasıdır. BQP ve BPP arasında bir kehanet ayrımı oluşturmak için tasarlanmıştır .

Simon'ın algoritması

Simon'ın algoritması, bir kara kutu problemini, sınırlı hata olasılıklı algoritmalar da dahil olmak üzere, herhangi bir klasik algoritmadan katlanarak daha hızlı çözer. Verimli olduğunu düşündüğümüz tüm klasik algoritmalar üzerinde üstel bir hızlanma sağlayan bu algoritma, Shor'un faktoring algoritmasının motivasyonuydu.

Kuantum fazı tahmin algoritması

Kuantum faz kestirim algoritması kapısına özvektör ve erişmek için bir kuantum durumu orantılı verilen yekpare bir kapının bir özvektörün eigenphase belirlemek için kullanılır. Algoritma, diğer algoritmalarda sıklıkla bir alt program olarak kullanılır.

Shor'un algoritması

Shor'un algoritması, ayrık logaritma problemini ve polinom zamanında tamsayı çarpanlarına ayırma problemini çözerken, en iyi bilinen klasik algoritmalar süper polinom zamanını alır. Bu sorunların P veya NP-complete olduğu bilinmemektedir . Aynı zamanda, en iyi bilinen klasik algoritmaların süper polinom zamanında çalıştığı polinom zamanında kara kutu olmayan bir problemi çözen birkaç kuantum algoritmasından biridir.

Gizli alt grup sorunu

Değişmeli gizli alt grup sorun çözme, örneğin Simon sorun olarak kuantum bilgisayar tarafından çözülebilir pek çok sorun, bir genellemedir Pell denklemi test temel ideal a halka R ve faktoringe . Değişmeli gizli alt grup problemi için bilinen verimli kuantum algoritmaları vardır. Grubun mutlaka değişmeli olmadığı daha genel gizli alt grup problemi, daha önce bahsedilen problemlerin ve çizge izomorfizminin ve belirli kafes problemlerinin bir genellemesidir . Değişken olmayan belirli gruplar için verimli kuantum algoritmaları bilinmektedir. Bununla birlikte, grafik izomorfizmi için verimli bir algoritma verecek olan simetrik grup ve belirli kafes problemlerini çözecek dihedral grup için hiçbir verimli algoritma bilinmemektedir .

Bozon örnekleme problemi

Deneysel bir konfigürasyondaki Bozon Örnekleme Problemi , orta sayıda bozonların (örn. ışık fotonları) tanımlı bir üniterlikle sınırlandırılmış çok sayıda çıkış moduna rastgele dağıldığını varsayar . O zaman sorun, bozonların girdi düzenlemesine ve Unitarity'ye bağlı olan çıktının olasılık dağılımının adil bir örneğini üretmektir. Klasik bir bilgisayar algoritması ile bu sorunu çözmek işlem gerektiren sürekli ya imkansız ya da engelleyici bir uzun zaman alabilir matris dönüşümü üniter. 2014 yılında, uygun bir kuantum hesaplanabilir doğrusal optik ağa girdi olarak tek foton durumları üretmeye yönelik mevcut teknoloji ve standart olasılıksal yöntemlerin kullanılabileceği ve çıktı olasılık dağılımının örneklenmesinin kuantum algoritmaları kullanılarak gözle görülür şekilde üstün olacağı önerildi . 2015 yılında, araştırma, örnekleme probleminin Fock durumu fotonları dışındaki girdiler için benzer karmaşıklığa sahip olduğunu öngördü ve tutarlı genlik girdilerinin boyutuna bağlı olarak, hesaplama karmaşıklığında klasik olarak simüle edilebilirden Bozon Örnekleme Problemi kadar sert bir geçiş tanımladı .

Gauss toplamlarını tahmin etme

Bir Gauss toplamı türüdür üstel toplamı . Bu toplamları tahmin etmek için en iyi bilinen klasik algoritma üstel zaman alır. Ayrık logaritma problemi Gauss toplam tahminine indirgendiğinden, Gauss toplamlarını tahmin etmek için verimli bir klasik algoritma, olası olmadığı düşünülen ayrık logaritmaların hesaplanması için verimli bir klasik algoritma anlamına gelir. Bununla birlikte, kuantum bilgisayarlar, Gauss toplamlarını polinom zamanında polinom kesinliği için tahmin edebilir.

Fourier balıkçılığı ve Fourier kontrolü

n bitlik dizileri bir Boole değerine eşleyen n rastgele Boole işlevinden oluşan bir kahinimiz var . Hadamard-Fourier dönüşümü için dizgelerin en az 3/4'ünü sağlayacak şekilde n n-bitlik dizgiler z 1 ,..., z n bulmamız gerekiyor.

ve en az 1/4 tatmin edici

Bu, sınırlı hata kuantum polinom zamanında (BQP) yapılabilir.

Genlik amplifikasyonuna dayalı algoritmalar

Genlik amplifikasyonu , bir kuantum durumunun seçilmiş bir alt uzayının amplifikasyonuna izin veren bir tekniktir. Genlik amplifikasyonunun uygulamaları genellikle karşılık gelen klasik algoritmalar üzerinde ikinci dereceden hızlanmalara yol açar. Grover'ın algoritmasının bir genellemesi olarak düşünülebilir.

Grover'ın algoritması

Grover'ın algoritması, klasik olarak gerekli sorgular yerine yalnızca sorguları kullanarak, işaretli bir giriş için N girişli yapılandırılmamış bir veritabanını (veya sırasız bir listeyi) arar . Klasik olarak, sınırlı hata olasılıklı algoritmalara izin veren sorgular bile gereklidir.

Teorisyenler, Bohm mekaniğindeki gizli değişkenlerin geçmişlerine erişebilen standart bir kuantum bilgisayarın varsayımsal bir genelleştirmesini düşündüler . (Bu tür bir bilgisayar tamamen varsayımsal olduğunu ve olacağını değil kuantum mekaniğinin standart teori altında standart bir kuantum bilgisayarı, hatta mümkün.) Böyle bir varsayımsal bilgisayar en az bir N-madde veritabanının bir arama uygulamak adımlar. Bu, Grover'ın algoritması tarafından atılan adımlardan biraz daha hızlıdır . Her iki arama yöntemi de kuantum bilgisayar modelinin polinom zamanında NP-tam problemlerini çözmesine izin vermez .

kuantum sayımı

Kuantum sayma , arama probleminin genelleştirilmesini çözer. Sadece var olup olmadığını tespit etmek yerine, sırasız bir listedeki işaretli girişlerin sayısını sayma problemini çözer. Spesifik olarak, bir -element listesindeki işaretli girişlerin sayısını, yalnızca sorgular yaparken hatayla birlikte sayar , burada listedeki işaretli öğelerin sayısı. Daha kesin olarak, algoritma aşağıdaki doğrulukla işaretlenmiş girişlerin sayısı için bir tahmin verir : .

Kuantum yürüyüşlerine dayalı algoritmalar

Kuantum yürüyüşü, bazı durumlar üzerindeki olasılık dağılımı ile tanımlanabilen klasik rastgele yürüyüşün kuantum analoğudur . Kuantum yürüyüşü, durumlar üzerinde bir kuantum süperpozisyonu ile tanımlanabilir . Kuantum yürüyüşlerinin bazı kara kutu problemleri için üstel hızlanmalar sağladığı bilinmektedir. Ayrıca birçok problem için polinom hızlandırmaları sağlarlar. Kuantum yürüyüş algoritmalarının oluşturulması için bir çerçeve mevcuttur ve oldukça çok yönlü bir araçtır.

Eleman ayırt edicilik sorunu

Öğe ayırt edicilik sorunu, bir listenin tüm öğelerinin farklı olup olmadığını belirleme sorunudur. Klasik olarak, Ω ( K ) sorguları boyutu bir listesi için gerekli olan N . Ancak, bir kuantum bilgisayardaki sorgularda çözülebilir . En uygun algoritma Andris Ambainis'e aittir . Yaoyun Shi , menzilin boyutu yeterince büyük olduğunda ilk önce sıkı bir alt sınır olduğunu kanıtladı. Ambainis ve Kutin bağımsız olarak (ve farklı kanıtlarla) çalışmalarını tüm fonksiyonlar için alt sınırı elde etmek için genişletti.

Üçgen bulma sorunu

Üçgen bulma problemi, verilen bir grafiğin bir üçgen ( 3 boyutlu bir klik ) içerip içermediğini belirleme problemidir . Kuantum algoritmaları için en iyi bilinen alt sınır Ω( N )'dir, ancak bilinen en iyi algoritma , önceki en iyi O( N 1.3 ) sorgularına göre bir gelişme olan O( N 1.297 ) sorguları gerektirir .

Formül değerlendirmesi

Formül, her bir iç düğümde bir kapı ve her yaprak düğümde bir girdi biti bulunan bir ağaçtır. Sorun, girişe Oracle erişimi verilen kök düğümün çıktısı olan formülü değerlendirmektir.

İyi çalışılmış bir formül, yalnızca NAND kapıları olan dengeli ikili ağaçtır. Bu formül türü, rastgelelik kullanan Θ( N c ) sorguları gerektirir , burada . Ancak bir kuantum algoritması ile Θ( N 0.5 ) sorgularında çözülebilir . Geleneksel olmayan Hamiltonian oracle modeli için bir tane bulunana kadar bu durum için daha iyi bir kuantum algoritması bilinmiyordu. Standart ayar için aynı sonuç hemen ardından geldi.

Daha karmaşık formüller için hızlı kuantum algoritmaları da bilinmektedir.

Grup değişebilirliği

Problem, k üreteci tarafından verilen bir kara kutu grubunun değişmeli olup olmadığını belirlemektir . Kara kutu grubu, grup işlemlerini (çarpma, ters çevirme ve özdeşlikle karşılaştırma) gerçekleştirmek için kullanılması gereken, oracle işlevine sahip bir gruptur. Sorunu çözmek için gereken Oracle çağrılarının sayısı olan sorgu karmaşıklığı ile ilgileniyoruz. Deterministik ve randomize sorgu karmaşıklığı vardır ve sırasıyla. Kuantum algoritması sorgular gerektirir, ancak en iyi bilinen algoritma sorguları kullanır .

BQP-tam sorunlar

Karmaşıklığı sınıfı BQP (sınırlı yanılma kuantum polinom zaman) setidir karar problemlerinin bir çözülemez kuantum bilgisayar olarak polinom zamanda tüm örnekler için en fazla 1/3 hata olasılığı olan. Klasik karmaşıklık sınıfı BPP'nin kuantum analoğudur .

Bir sorun BQP o ise -tamamlamak BQP ve herhangi bir sorun BQP edilebilir azaltılmış kendisine polinom zamanda . Gayrı, sınıfı BQP -tamamlamak sorunların en zor sorunlardan kadar sert olanlardır BQP ve kendilerini (sınırlı hata ile) bir kuantum bilgisayar tarafından verimli bir şekilde çözülebilir.

Düğüm değişmezlerini hesaplama

Witten, Chern-Simons topolojik kuantum alan teorisinin (TQFT) Jones polinomları cinsinden çözülebileceğini göstermişti . Bir kuantum bilgisayar bir TQFT'yi simüle edebilir ve böylece bildiğimiz kadarıyla en kötü senaryoda klasik olarak hesaplanması zor olan Jones polinomunu yaklaşık olarak tahmin edebilir.

kuantum simülasyonu

Kuantum bilgisayarların klasik bilgisayarlardan daha güçlü olabileceği fikri, Richard Feynman'ın klasik bilgisayarların çok parçacıklı kuantum sistemlerini simüle etmek için üstel zamana ihtiyaç duyduğu gözleminden kaynaklandı. O zamandan beri, kuantum bilgisayarların kuantum fiziksel süreçleri klasik bilgisayarlardan katlanarak daha hızlı simüle edebildiği fikri büyük ölçüde ete kemiğe büründü ve detaylandırıldı. Hem Bozonik hem de Fermiyonik sistemleri simüle etmek için verimli (yani polinom zamanlı) kuantum algoritmaları geliştirilmiştir ve özellikle, mevcut klasik süper bilgisayarların yeteneklerinin ötesinde kimyasal reaksiyonların simülasyonu sadece birkaç yüz kübit gerektirir. Kuantum bilgisayarlar ayrıca topolojik kuantum alan teorilerini verimli bir şekilde simüle edebilir. Bu sonuç, içsel ilgisine ek olarak, Jones ve HOMFLY polinomları ve üç boyutlu manifoldların Turaev-Viro değişmezi gibi kuantum topolojik değişmezleri tahmin etmek için verimli kuantum algoritmalarına yol açmıştır .

Lineer denklem sistemlerini çözme

2009 yılında Aram Harrow , Avinatan Hassidim ve Seth Lloyd , lineer sistemleri çözmek için bir kuantum algoritması formüle ettiler . Algoritma , verilen denklem lineer sistemde çözüm vektörü üzerinde skaler ölçümün sonucunu tahmin eder.

Doğrusal sistemin seyrek olması ve düşük koşul sayısına sahip olması ve kullanıcının çözüm vektörünün kendi değerleri yerine çözüm vektörü üzerindeki skaler ölçümün sonucuyla ilgilenmesi koşuluyla , algoritmanın çalışma süresi , lineer sistemdeki değişkenlerin sayısı nerede . Bu, çalışan (veya pozitif yarı tanımlı matrisler için) en hızlı klasik algoritma üzerinde üstel bir hızlanma sunar .

Hibrit kuantum/klasik algoritmalar

Hibrit Kuantum/Klasik Algoritmalar, kuantum durum hazırlama ve ölçümü klasik optimizasyonla birleştirir. Bu algoritmalar genellikle bir Hermitian Operatörün temel durum özvektörünü ve özdeğerini belirlemeyi amaçlar.

QAOA

Kuantum yaklaşık optimizasyon algoritması grafik teorisi sorunları çözmek için kullanılabilir kuantum tavlama bir oyuncak modelidir. Algoritma, bir amaç fonksiyonunu maksimize etmek için kuantum işlemlerinin klasik optimizasyonunu kullanır.

Varyasyonel kuantum öz-çözücü

VQE algoritması , bir molekülün temel durum enerjisini bulmak için bir ansatz durumunun enerji beklentisini en aza indirmek için klasik optimizasyon uygular . Bu, moleküllerin uyarılmış enerjilerini bulmak için de genişletilebilir.

Sözleşmeli kuantum öz-çözücü

CQE algoritması, bir molekülün temel veya uyarılmış durum enerjisini ve iki elektronlu indirgenmiş yoğunluk matrisini bulmak için iki (veya daha fazla) elektronun uzayı üzerine Schrödinger denkleminin büzülmesinin (veya projeksiyonunun) kalıntısını en aza indirir. Enerjileri ve iki elektronlu azaltılmış yoğunluk matrislerini doğrudan anti-Hermitian sözleşmeli Schrödinger denkleminden çözmek için klasik yöntemlere dayanmaktadır.

Ayrıca bakınız

Referanslar

Dış bağlantılar

anketler