Solovay-Kitaev teoremi - Solovay–Kitaev theorem

Kuantum bilgileri ve hesaplama olarak, Solovay-Kitaev teoremi tek bir dizi takdirde, kabaca, diyor qubit kuantum kapıları bir üretir yoğun alt kümesi içinde SU (2) kümesinin herhangi hızla hangi araçları SU (2) doldurmak için garanti o istenen kapı, jeneratör setinden oldukça kısa bir kapı dizisi ile yaklaştırılabilir. Robert M. Solovay ilk olarak sonucu 1995 yılında bir e-posta listesinde duyurdu ve Alexei Kitaev 1997'de bağımsız olarak kanıtının bir taslağını verdi. Christopher M. Dawson ve Michael Nielsen teoremi kuantum alanındaki en önemli temel sonuçlardan biri olarak adlandırıyor. hesaplama .

Bu teoremin bir sonucu, sabit kübit kapılarının bir kuantum devresinin, istenen bir sonlu evrensel geçit kümesinden bir kuantum devresi tarafından hataya ( operatör normunda ) yaklaştırılabilmesidir . Karşılaştırma yaparsak, sadece bir geçit kümesinin evrensel olduğunu bilmek, yalnızca sabit-kübit kapıların, uzunluğunda sınır olmaksızın, geçit kümesinden sonlu bir devre ile yaklaşılabileceğini ima eder. Bu nedenle, Solovay-Kitaev teoremi, bu yaklaşımın şaşırtıcı derecede verimli hale getirilebileceğini gösteriyor , böylece kuantum bilgisayarların kuantum hesaplamanın tam gücünü elde etmek için yalnızca sınırlı sayıda kapıya ihtiyaç duyduğunu doğruluyor . ${\ displaystyle m}$${\ displaystyle \ varepsilon}$${\ displaystyle O (m \ log ^ {c} (m / \ varepsilon))}$

Beyan

SU (2) ' de kendi terslerini içeren (öyle ima eden ) ve ürettikleri grup SU (2)' de yoğun olacak şekilde sonlu bir elemanlar kümesi olsun . Biraz düşünün . Sonra bir sabit vardır ki, herhangi biri için , uzunluktan bir dizi kapı vardır, öyle ki . Yani, operatör norm hatasına yaklaşıktır . ${\ displaystyle {\ mathcal {G}}}$${\ mathcal {G}}} içinde {\ displaystyle g \$${\ mathcal {G}}} içinde {\ displaystyle g ^ {- 1} \$${\ displaystyle \ langle {\ mathcal {G}} \ rangle}$${\ displaystyle \ varepsilon> 0}$${\ displaystyle c}$$\ mathrm {SU} (2)} içinde {\ displaystyle U \$${\ displaystyle S}$${\ displaystyle {\ mathcal {G}}}$${\ displaystyle O (\ log ^ {c} (1 / \ varepsilon))}$${\ displaystyle \ | SU \ | \ leq \ varepsilon}$${\ displaystyle S}$${\ displaystyle U}$

Niceliksel sınırlar

Sabit , herhangi bir sabit için yapılabilir . Bununla birlikte, alabileceğimiz belirli kapı setleri vardır , bu da kapı dizisinin uzunluğunu sabit bir faktöre kadar sıkı hale getirir. ${\ displaystyle c}$${\ displaystyle 3+ \ delta}$${\ displaystyle \ delta> 0}$${\ displaystyle c = 1}$

Kanıt fikri

Solovay-Kitaev teoreminin kanıtı, giderek daha iyi yaklaşımlar veren bir kapı dizisini yinelemeli olarak inşa ederek ilerler . Böyle bir yaklaşımımız olduğunu varsayalım . Amacımız , hataya yaklaşan bir dizi kapı bulmaktır . Bu kapı dizisini birleştirerek , öyle bir dizi kapı elde ederiz . ${\ displaystyle U \ in \ operatorname {SU} (2)}$${\ displaystyle U_ {n-1} \ in \ operatorname {SU} (2)}$${\ displaystyle \ | U-U_ {n-1} \ | \ leq \ varepsilon _ {n-1}}$${\ displaystyle UU_ {n-1} ^ {- 1}}$${\ displaystyle \ varepsilon _ {n}}$${\ displaystyle \ varepsilon _ {n} <\ varepsilon _ {n-1}}$${\ displaystyle U_ {n-1}}$${\ displaystyle U_ {n}}$${\ displaystyle \ | U-U_ {n} \ | \ leq \ varepsilon _ {n}}$

Temel fikir, kimliğe yakın öğelerin komütatörlerine "beklenenden daha iyi" yaklaşılabilmesidir. Özellikle, tatmin edici ve tatmin edici yaklaşımlar için ve sonra ${\ displaystyle V, W \ in \ operatorname {SU} (2)}$${\ displaystyle \ | VI \ | \ leq \ delta _ {1}}$${\ displaystyle \ | WI \ | \ leq \ delta _ {1}}$${\ displaystyle {\ tilde {V}}, {\ tilde {W}} \ in \ operatorname {SU} (2)}$${\ displaystyle \ | V - {\ tilde {V}} \ | \ leq \ delta _ {2}}$${\ displaystyle \ | W - {\ tilde {W}} \ | \ leq \ delta _ {2}}$

${\ displaystyle \ | VWV ^ {- 1} W ^ {- 1} - {\ tilde {V}} {\ tilde {W}} {\ tilde {V}} ^ {- 1} {\ tilde {W} } ^ {- 1} \ | \ leq O (\ delta _ {1} \ delta _ {2}),}$

nerede büyük O gösterimi gizler yüksek mertebeden terimler. Yukarıdaki ifadenin olması saf bir şekilde sınırlandırılabilir , ancak grup komütatör yapısı önemli hata iptali yaratır. ${\ displaystyle O (\ delta _ {2})}$

Bu gözlemi, bir grup komütatörü olarak yaklaştırmak istediğimiz ifadeyi yeniden yazarak kullanıyoruz . Bu, her ikisi de ve kimliğe yakın olacak şekilde yapılabilir (çünkü ). Biz yinelemeli hesaplama kapı dizileri yaklaşan Yani, eğer ve hiç hata, biz yaklaşan bir kapı dizisini almak istenen daha iyi hassasiyet için birlikte . Yeterince uzun kapı dizilerinin tümünün kaba kuvvet hesaplamasıyla sabit bir temel durum yaklaşımı elde edebiliriz . ${\ displaystyle UU_ {n-1} ^ {- 1} = V_ {n-1} W_ {n-1} V_ {n-1} ^ {- 1} W_ {n-1} ^ {- 1}}$${\ displaystyle V_ {n-1}}$${\ displaystyle W_ {n-1}}$${\ displaystyle \ | UU_ {n-1} ^ {- 1} -I \ | \ leq \ varepsilon _ {n-1}}$${\ displaystyle V_ {n-1}}$${\ displaystyle W_ {n-1}}$${\ displaystyle \ varepsilon _ {n-1}}$${\ displaystyle UU_ {n-1} ^ {- 1}}$${\ displaystyle \ varepsilon _ {n}}$${\ displaystyle \ varepsilon _ {n}}$${\ displaystyle \ varepsilon _ {0}}$

Referanslar