Powszechnie wiadomo, że losowy spacer w dwuwymiarowej siatce powróci do początku z prawdopodobieństwem 1. Wiadomo również, że ten sam losowy spacer w TRZY wymiarach ma prawdopodobieństwo mniej niż 1 powrotu do początku . Moje pytanie brzmi: Czy jest coś pomiędzy? Załóżmy na przykład, że moja...
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,...
Czas dojazdu na połączonym wykresie definiuje się jako oczekiwaną liczbę kroków w losowym marszu rozpoczynającym się od , przed odwiedzeniem węzła a następnie ponownie osiągnięciem węzła . Jest to w zasadzie suma dwóch czasów uderzenia i .i j i H ( i , j ) H ( j , i...
Interesują mnie właściwości losowo ukierunkowanych wykresów o ustalonym out-stopniu ddd . Wyobrażam sobie losowy model wykresu, w którym każdy wierzchołek wybiera u sąsiadów (powiedzmy z zamiennikiem) Pytanie : Czy coś wiadomo o rozkładzie stacjonarnym i czasach mieszania losowych spacerów na...
Biorąc pod uwagę losowy spacer na wykresie, czas pokrycia jest pierwszym (oczekiwana liczba kroków), że każdy wierzchołek został trafiony (pokryty) przez spacer. W przypadku podłączonych niekierowanych wykresów czas pokrycia jest znany z górnej granicy . Istnieją silnie połączone digrafy z...
W artykule Kwantowe losowe spacery uderzają wykładniczo szybciej ( arXiv: quant-ph / 0205083 ) Kempe podaje pojęcie czasu uderzenia w spacery kwantowe (w hipersześcianie), które nie jest zbyt popularne w literaturze dotyczącej spacerów kwantowych. Jest on zdefiniowany w następujący sposób:...
Szybka wersja Czy istnieją modele dekoherencji na spacer kwantowej na linii takie, że możemy dostroić dojść do rozprzestrzeniania się jako za każdy 1 / 2 ≤ k ≤ 1 ?Θ ( tk)Θ(tk)\Theta(t^k)1 / 2 ≤ k ≤ 11/2≤k≤11/2 \leq k \leq 1 Motywacja Klasyczne losowe spacery są przydatne w projektowaniu...
Niech będzie nieregularnym połączonym wykresem, którego stopień jest ograniczony. Załóżmy, że każdy węzeł zawiera unikalny token.G = ( V, E)G=(V,E)G= (V, E) Chcę równomiernie tasować tokeny między wykresami, używając tylko lokalnych zamian (tj. Wymiany tokenów między dwoma sąsiadującymi węzłami)?...
Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach.n mG=(V,E)sol=(V.,mi)G=(V,E)nnnmmm Próbuję określić czas oczekiwany prowadzeniem algorytmu Wilsona do generowania losowych rozpinające drzewo . Tam pokazano, że to , gdzie to średni czas uderzenia : gdzie:O ( τ )...
Rozważ następujący problem. nnnv1,⋯,vn∈Rv1,⋯,vn∈Rv_1, \cdots, v_n \in \mathbb{R}S⊆{1,⋯,n}S⊆{1,⋯,n}S \subseteq \{1,\cdots,n\}maxi∈Svimaxi∈Svi\max_{i \in S} v_i Ten problem jest prosty: możemy użyć wyszukiwania binarnego, aby znaleźć argmax z zapytaniami . tj. Zbuduj kompletne drzewo binarne z...
W przypadku projektu, nad którym pracuję, powinienem wygenerować losowo rozciągające się drzewa o ograniczonej wysokości. Zasadniczo wykonuję następujące czynności: 1) Wygeneruj drzewo opinające 2) Sprawdź wykonalność, jeśli to możliwe, zachowaj ją. 1) Zaczynając od minimalnego drzewa...
(Na moje pierwotne pytanie wciąż nie ma odpowiedzi. Dodałem dalsze wyjaśnienia.) Analizując losowe spacery (na niekierowanych grafach), widząc losowy spacer jako łańcuch Markowa, wymagamy, aby wykres nie był dwustronny, aby obowiązywało podstawowe twierdzenie o łańcuchach Markowa. Co się stanie,...
Szukam twierdzenia, które mówi coś takiego: jeśli czas pokrycia odwracalnego łańcucha Markowa jest mały, to szczelina widmowa jest duża. Tutaj oznacza lukę widmową1 - |λ2)|1-|λ2)|1-|\lambda_2|oznacza to, że ignorujemy najmniejszą wartość własną łańcucha. Jedyny wynik, jaki udało mi się znaleźć w...