Quantum Entanglement: A Deep Dive

Graf zbudowany z rzutów monet

Weź N oddzielnych węzłów i, dla każdej pary spośród N(N-1)/2 możliwych połączeń, połącz je niezależnie krawędzią o prawdopodobieństwie p. To jest cała recepta na graf Erdos-Renyi G(N,p), wprowadzony przez Paula Erdosa i Alfreda Reniego w 1959 roku (z równoważnym modelem uniformnym badany przez Edgara Gilberta to samo lata). Żaden węzeł nie jest specjalny, żadna krawędź nie ma większej szansy niż inna – a jednak, gdy p przekracza pojedynczy ostry próg, globalny kształt grafu zmienia się z rozszczepienia na małe fragmenty w jeden dominujący glob,

Ten przełom to przejście fazowe, używane dla wody zamienianej na parę – i dlatego przepływ pokazuje się wszędzie, od epidemiologii po naukę o materiałach: jest to najprostszy możliwy model tego, jak lokalne połączenia sumują się w globalną łączność.

Liczenie krawędzi, nie węzłów

Parametr kontroli, który ma znaczenie, to nie p samo w sobie, ale średnia stopień, c = p(N-1), która jest w przybliżeniu równa pN dla dużych N - oczekana liczba krawędzi dotykających typowego węzła. Erdos i Renyi udowodnili, że rozmiar największej składowej podycznej ulega nagłej zmianie dokładnie w c = 1, czyli w p_c = 1/N.

c < 1 (p < 1/N): każda składowa jest mała - największa wynosi O(log N) węzłów c = 1 (p = 1/N): punkt krytyczny - rozmiary składowych podycyjnych mają postać prawego rozkładu potęgowego c > 1 (p > 1/N): pojawia się pojedyncza, gigantyczna składowa, jej rozmiar proporcjonalny do N Poniżej progu graf jest lasem małych drzew i cykli - żaden z elementów nie zajmuje więcej niż logarytmiczną części węzłów, a dodawanie kolejnych krawędzi tworzy tylko więcej małych kawałków. Przekroczenie c = 1 powoduje kondensację gigantycznej składowej z szumu niemal natychmiast: jej rozmiar rośnie z O(log N) do ułamka całej grafu w oknie wartości p, które kurczy się wraz ze wzrostem N. Jest to ukryty argument dotyczący procesu rozgałęziania - każdy węzeł, którego badamy z danego wierzchołka, średnio otwiera c nowych krawędzi, a proces rozgałęziania z średnią liczbą potomstwa c umiera na pewno, jeśli c jest nie większa niż 1, ale przeżywa z pewną prawdopodobieństwem, jeśli c przekracza 1.

c < 1  (p < 1/N):  every component is small - the largest is O(log N) nodes
c = 1  (p = 1/N):  the critical point - component sizes follow a power law
c > 1  (p > 1/N):  a single giant component emerges, size proportional to N

Jak wygląda gigantyczny składnik

Tuż nad progowym poziomem gigantyczny składnik wciąż jest kruchy: jego względny rozmiar s spełnia równanie s = 1 - e^(-cs), gdzie c jest transcendentne i daje s bliskie zeru tuż po c = 1, a s zbliża się do 1, gdy c rośnie powyżej 3 lub 4. Wtedy właśnie rozkład wielkości składnika w punkcie c = 1 odpowiada prawu potęgowemu z wykładnikiem -5/2, co jest znakiem krytycznego układu bez charakterystycznej skali – tego samego wykładnika, który pojawia się również w modelach średniej wartości percolacji i procesów rozgałęziania.

Jest to również, nieprzypadkowo, matematyka stojąca za podstawowym współczynnikiem reprodukcji R0 dla epidemii. Jeśli każdy zarażony człowiek zarazia średnio R0 innych osób, gdzie R0 jest mniejsze niż 1, łańcuch infekcji gaśnie (podkrytyczny), a R0 jest większe niż 1, możliwe jest wybuch epidemiczny (nadkrytyczny) – model SIR na sieci kontaktów losowych prawie w całości redukuje się do percolacji wiązywania z p związanym z prawdopodobieństwem transmisji.

Losowe grafy w porównaniu z rzeczywistymi sieciami

Rzeczywiste sieci społeczne, biologiczne i infrastrukturalne nie są grafami Erdos-Reniego – mają znacznie więcej węzłów o wysokim stopniu niż przewiduje rozkład Poissona, zwykle bliższe prawu potęgowemu (model preferencji Barabasi-Alberta jest tutaj preferowanym modelem). Ta różnica ma poważną konsekwencję praktyczną odkrytą przez Reka Albert, Hawoong Jeong i Alberta-Laslo Barabasi w 2000 roku: sieci o podziale skali są niezwykle odporne na losowe usunięcie węzłów – usuwanie losowych węzłów prawie nie wpływa na dużą komponentę, ponieważ większość węzłów ma niski stopień – ale kruche wobec ukierunkowanego usuwania węzłów o najwyższym stopniu, które może zniszczyć połączenie już po usunięciu niewielkiej liczby węzłów. Graf Erdos-Reniego, z drugiej strony, jest równie podatny (lub równie odporny) na ataki losowe i ukierunkowane, ponieważ każdy węzeł wygląda statystycznie tak samo.

Symulacja

dla i w zakresie(N): dla j w zakresie(i + 1, N): jeżeli random() < p: dodaj_krawędź(i, j) # algorytm union-find śledzi rozmiary komponentów w ~O(N alpha(N)) podczas dodawania krawędzi znajdź_największy_rozmiar_komponentu() Śledź największy rozmiar komponentu przy użyciu struktury union-find, gdy krawędzie są dodawane pojedynczo (zamiast ponownie obliczać łączności od zera po każdej krawędzi) i możesz obserwować kondensację dużego komponentu w czasie rzeczywistym - płótno powyżej dodaje krawędzie ze stałą częstotliwością i aktualizuje rozmiary komponentów, więc moment, gdy c przekracza 1, pojawia się jako widoczny skok zamiast stopniowej zmiany.

for i in range(N):
    for j in range(i + 1, N):
        if random() < p:
            add_edge(i, j)
# union-find tracks component sizes in ~O(N alpha(N)) as edges are added
find_largest_component_size()

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Network Percolation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.