Pytania otagowane jako quantum-computing

Obliczenia kwantowe i zagadnienia obliczeniowe związane z mechaniką kwantową

4
Algorytmy kwantowej aproksymacji
Ogólnie uważa się za mało prawdopodobne, aby komputery kwantowe były w stanie skutecznie rozwiązywać problemy związane z NP. W klasycznym przypadku jednym podejściem do rozwiązania takich problemów jest zastosowanie algorytmów aproksymacyjnych. Czy były jakieś badania algorytmów aproksymacyjnych wykorzystujących obliczenia kwantowe, w których kwantowość znacznie przyspiesza w porównaniu z klasycznymi metodami …
2
Jaka jest najlepsza dolna granica progu tolerancji błędów w obliczeniach kwantowych?
Jest dobrze ustalone, że istnieje próg szumowy dla obliczeń kwantowych, taki że poniżej tego progu obliczenia mogą być zakodowane w taki sposób, że dają poprawny wynik z ograniczonym prawdopodobieństwem (z co najwyżej wielomianowym narzutem obliczeniowym). Próg ten zależy od zastosowanego kodowania i dokładnej natury hałasu, i często wyniki symulacji dają …
2
Złożoność obliczeniowa optyki kwantowej
W „Wymaganiu do obliczeń kwantowych” Bartlett i Sanders podsumowują niektóre ze znanych wyników obliczeń ciągłych zmiennych kwantowych w poniższej tabeli: MOJE pytanie jest trzykrotne: Czy dziewięć lat później można wypełnić ostatnią komórkę? Jeśli kolumna zostanie dodana z tytułem „Universal for BQP”, jak wyglądałaby reszta kolumny? Czy 95-stronicowe arcydzieło Aaronsona i …
3
Czy możemy kwantyfikować „stopień kwantowości” w algorytmie kwantowym?
Splątanie jest często utrzymywane jako kluczowy składnik, który sprawia, że ​​algorytmy kwantowe są dobrze ... kwantowe, i można to prześledzić do stanów Bella, które niszczą ideę fizyki kwantowej jako modelu probabilistycznego w stanie ukrytym. W teorii informacji kwantowej (z mojego raczej słabego zrozumienia) splątanie może być również wykorzystane jako konkretny …
1
Losowa złożoność zapytań problemu drzew połączonych
Ważny artykuł z 2003 roku autorstwa Childsa i in.wprowadził „problem drzew połączonych”: problem dopuszczający wykładnicze przyspieszenie kwantowe, który nie jest podobny do żadnego innego znanego nam problemu. W tym problemie otrzymaliśmy wykładniczo duży wykres, taki jak ten pokazany poniżej, który składa się z dwóch kompletnych dwójkowych drzewek głębokości n, których …
1
Pobieranie próbek zadowalających wzorów 3-SAT
Rozważ następujące zadanie obliczeniowe: Chcemy pobrać próbkę 3-SAT formuły zmiennych (wariant: zmiennych klauzule m ) w odniesieniu do równomiernego rozkładu prawdopodobieństwa, pod warunkiem spełnienia wzoru:nnnnnnmmm P1: Czy można to skutecznie osiągnąć za pomocą klasycznego komputera (z losowymi bitami)? P2: Czy można to skutecznie osiągnąć za pomocą komputera kwantowego? Interesują mnie …
5
Uniwersalne zestawy bram do SU (3)?
W obliczeniach kwantowych często interesują nas przypadki, w których grupa specjalnych operatorów unitarnych, G, dla jakiegoś systemu d-wymiarowego daje dokładnie całą grupę SU (d), a nawet tylko przybliżenie zapewniane przez gęstą osłonę SU (d). Grupa skończonego rzędu, taka jak grupa Clifforda dla układu d-wymiarowego C (d), nie zapewni gęstej osłony. …
1
Próbkowanie w przybliżeniu z wypukłych wielościanów za pomocą komputerów kwantowych
Komputery kwantowe są bardzo dobre do dystrybucji próbkowania, których nie wiemy jak próbkować przy użyciu klasycznych komputerów. Na przykład, jeśli f jest funkcją logiczną (od do ), którą można obliczyć w czasie wielomianowym, to za pomocą komputerów kwantowych możemy skutecznie próbkować zgodnie z rozkładem opisanym przez Rozwinięcie Fouriera f. (Nie …
1
W jaki sposób papier BosonSampling unika łatwych klas złożonych matryc?
W złożoności obliczeniowej optyki liniowej ( ECCC TR10-170 ) Scott Aaronson i Alex Arkhipov twierdzą, że jeśli komputery kwantowe mogą być skutecznie symulowane przez klasyczne komputery, hierarchia wielomianowa upadnie na trzeci poziom. Problemem motywującym jest próbkowanie z rozkładu określonego przez sieć liniowo-optyczną; rozkład ten można wyrazić jako stały dla określonej …
1
Ile mocy obliczeniowej mieści się w centymetr sześcienny?
To pytanie stanowi odpowiedź na pytanie o algorytmy DNA zadane przez Aaditę Mehrę . W komentarzach Joe Fitzsimmons powiedział częściowo: Promień układu musi być skalowany proporcjonalnie do masy, aby tego uniknąć. Moc obliczeniowa jest skalowana co najwyżej liniowo w masie. Zatem twoja wykładnicza ilość maszyn ma wykładniczy promień. Ponieważ nie …
1
Konsekwencje ?
Chociaż twierdzenie Adlemana pokazuje, że , nie znam żadnej literatury badającej możliwe włączenie . Jakie konsekwencje teoretyczne pod względem złożoności miałoby takie włączenie?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP} \subseteq \mathsf{P}/\text{poly} Twierdzenie Adlemana jest czasem nazywane „protoplastą argumentów derandomizacji”. Uważa się, że podlega derandomizacji, podczas gdy nie ma dowodów na to, że „kwantowość” mogłaby …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.