Bioinformatyczne podejście do przewidywania raka z wykorzystaniem algorytmu klastrowania kwantowego do podobieństwa behawioralnego ekspresji genów

Podsumowanie

Protokół ten ma na celu klasteryzację danych o ekspresji genów do klasyfikacji nowotworów za pomocą algorytmu Hybrid Quantum K-Means, który automatycznie wykrywa optymalną liczbę klastrów i efektywnie je rozdziela, co przyspiesza zastosowania bioinformatyczne na szumowych urządzeniach kwantowych o szumie średniej skali (NISQ).

Streszczenie

Niniejsze badanie wprowadza hybrydowy kwantowy algorytm klastrowania K-Means z automatycznym wykrywaniem klastrów do klasyfikacji danych o ekspresji genów nowotworowych i nienowotworowych. Metoda wykorzystuje kwantowe mapowanie wielofunkcyjne do kodowania stanów, estymację odległości kwantowej opartą na teście swap oraz optymalizację opartą na gradientach kwantowych do dynamicznej identyfikacji optymalnej liczby klastrów poprzez minimalizację wariancji wewnątrzklasterowej. Początkowe ogniska są wybierane za pomocą strategii proporcjonalnej odległości prawdopodobieństwa, co poprawia stabilność i dokładność. Stosowane do zbiorów danych dotyczących raka piersi, podejście to przewyższa istniejący kwantowy algorytm K-Means, osiągając Silhouette Score 0,641 (w porównaniu do 0,601), Calinski-Harabasz Index 766,57 (w porównaniu do 617,65) oraz Davies-Bouldin Index 0,659 (w porównaniu do 0,704). Wyniki te wskazują na lepszą zwartą i separację klastrów. Chociaż proponowany algorytm wykazuje nieco wyższą złożoność czasową O (N×_{K max}×M_obs) dzięki iteracyjnej optymalizacji, znacząco przewyższa predefiniowane K-K kwantowe K-Means pod względem dokładności klasteryzacji, redukcji błędów i praktycznej wykonalności. Jego efektywność w obsłudze danych wysokowymiarowych oraz odporność na szum kwantowy podkreślają potencjał dla praktycznych zastosowań bioinformatycznych, szczególnie w klasyfikacji nowotworów z wykorzystaniem profili ekspresji genów.

Wprowadzenie

W inżynierii biomedycznej, bioinformatyce, statystyce, naukach społecznych i ekonomii klasteryzacja jest podstawową techniką organizowania danych w znaczące, jednorodne grupy. Na przykład analiza danych topologicznych (TDA) została zastosowana do zbiorów danych o ekspresji genów nowotworowych, aby ujawnić wzorce strukturalne w przestrzeniach o wysokich wymiarach.¹. Klasteryzacja organizuje dane tak, że obiekty o dużym podobieństwie są umieszczane w tym samym klastrze, podczas gdy obiekty niepodobne przypisane są do różnych klastrów. To zalicza się do nauki bez nadzoru i nie wymaga oznaczonych danych treningowych.

W ciągu ostatnich kilku dekad opracowano liczne algorytmy klastrowania. Klasyczne podejścia obejmują klastrowanie oparte na partycjach²˒³, klastrowanie oparte na gęstości ^4,5, klastrowanie hierarchiczne ^6,7, klastrowanie oparte na siatce⁸˒⁹ oraz klastrowanie modelowe¹⁰. Recenzje tych metod podkreślają ich mocne strony, ale także ograniczenia¹¹. Chociaż są skuteczne w określonych kontekstach, większość klasycznych algorytmów ma trudności z danymi o wysokich wymiarach, szumie lub nieregularnie rozłożonymi. W konsekwencji nie istnieje uniwersalna metoda klastrowania, która działałaby optymalnie we wszystkich typach danych.

Aby sprostać tym wyzwaniom, klasteryzacja kwantowa wyłoniła się jako obiecująca alternatywa¹². W przeciwieństwie do klasycznych algorytmów, podejścia inspirowane kwantowością wykorzystują superpozycję, splątanie i inne zasady mechaniki kwantowej, aby efektywniej badać przestrzenie danych. Ten paradygmat jest coraz bardziej akceptowany w środowisku badawczym¹³˒¹⁴˒¹⁵˒¹⁶˒¹⁷˒¹⁸, ponieważ wykazuje potencjalne przewagi nad klasterowaniem klasycznym w obsłudze wysokowymiarowych i szumowych zbiorów danych. Niemniej jednak istniejące metody klastrowania kwantowego często cierpią na zdefiniowaną liczbę klastrów lub niestabilną inicjalizację centroidów, co zmniejsza ich odporność w praktycznych zastosowaniach.

W tej pracy wprowadzono nowatorski algorytm hybrydowego klastrowania kwantowego K-Means oparty na podziałach, który obejmuje cztery odrębne innowacje: (i) Quantum Multi-Feature Mapping do kodowania danych ekspresji genów w wysokowymiarowej przestrzeni Hilberta; (ii) inicjalizację centroidów opartą na proporcjonalności proporcjonalnej prawdopodobieństwa, poprawiającą stabilność w porównaniu z inicjalizacją losową; (iii) Estymacja odległości kwantowej oparta na teście Swap dla dokładnego pomiaru podobieństwa; oraz (iv) optymalizacja oparta na gradientach kwantowych do dynamicznego określania optymalnej liczby klastrów poprzez minimalizację wariancji wewnątrzklastrowej. Te wkłady odróżniają proponowaną metodę od wcześniejszych podejść do klasteryzacji kwantowej^19,20, zwiększając jej odporność, skalowalność i zastosowanie w rzeczywistych scenariuszach bioinformatycznych.

Klasteryzowanie danych o ekspresji genów jest kluczowym zadaniem w bioinformatyce, szczególnie w rozróżnianiu komórek nowotworowych i nienowotworowych na podstawie ich profili genetycznych. Tradycyjne metody klastrowania, takie jak klasyczne K-Means, często mają trudności z wysokowymiarowym charakterem zbiorów danych o ekspresji genów, co prowadzi do klasyfikacji suboptymalnej. Aby pokonać te wyzwania, wprowadzamy Quantum K-Means Algorithm with Optimal Cluster Determination, który wykorzystuje mapowanie cech kwantowych oraz probabilistyczną inicjalizację centroidów, aby osiągnąć lepszą wydajność klastrowania. Ten algorytm nie tylko efektywnie klastruje dane ekspresji genów, ale także automatycznie określa optymalną liczbę klastrów, umożliwiając identyfikację odrębnych podtypów nowotworów

Proponowany algorytm jest stosowany do zbiorów danych zawierających zarówno profile ekspresji genów nowotworowych, jak i nienowotworowych, klasteryzując je na podstawie podobieństwa behawioralnego w celu oceny jego skuteczności.

Protokół

1. Mapowanie cech kwantowych

Kodowanie klasycznych punktów danych w stany kwantowe odbywa się poprzez odwzorowanie ich na kwantową przestrzeń Hilberta, do której komputer kwantowy może efektywnie uzyskać dostęp i ją manipulować¹⁶˒^17,19. Proces ten wykorzystuje nieliniową mapę cech kwantowych, która osadza dane klasyczne w przestrzeni Hilberta (Rysunek 1). Stała mapa cech obwodów kwantowych przekształca punkty danych wejściowych w stany^{kwantowe 17}, podczas gdy układy wariacyjne umożliwiają zadania uczenia maszynowego poprzez adaptację bazy pomiarowej²². Układ wariacyjny składa się z zestawu parametryzowanych bramek kwantowych, zoptymalizowanych za pomocą hybrydowych technik kwantowo-klasycznych²³.

Rysunek 1: Mapowanie cech w kwantowej przestrzeni Hilberta. Proszę kliknąć tutaj, aby zobaczyć większą wersję tej figurki.

2. Kodowanie punktu docelowego i centroidów w kubitach

Aby zakodować cechy naszych punktów danych, musimy wykonać obroty za pomocą bramek U3.

To odwraca kubit θ radian od dodatniej osi z, a Φ radiany od dodatniej osi x.

Wszystkie kubity były inicjalizowane w stanie ∣0〉 przed rozpoczęciem procesu kodowania. Każda wartość ekspresji genu była normalizowana do zakresu [0,1] i przekształcana w kąt obrotu za pomocą relacji θ_i=πx_i. Następnie do każdego kubitu zastosowano parametryzowaną bramkę unitarną do zakodowania odpowiadającej cechy, zaimplementowanej w Qiskit za pomocą operacji qc.u(theta_i, pi, pi, qubit_index). Gdy kodowano wiele cech, procedura rotacji była powtarzana na odpowiednich kubitach, aby uzyskać wielofunkcyjną reprezentację. Po tych operacjach powstały stan kwantowy ∣ψ〉 reprezentował zakodowany wektor cech w przestrzeni Hilberta. Na tym etapie nie przeprowadzono pomiaru, ponieważ przygotowany stan był zarezerwowany do późniejszej estymacji podobieństwa.

3. Porównanie stanów kwantowych

Wyniki eksperymentów kwantowych są z natury losowe, ponieważ kubity są z natury niestabilne, jak opisuje fizyka kwantowa. W konsekwencji wnioski i prognozy muszą być wyrażane w kategoriach prawdopodobieństw i niepewności. Wyciąganie jednoznacznych wniosków stanowi więc realne wyzwanie. Jednak gdy rozważane stany kwantowe są czyste, różnice między stanami (z niezerowym prawdopodobieństwem) można jednoznacznie przewidzieć za pomocą eksperymentów²⁴˒²⁵.

Dwa stany kwantowe, ∣ψ〉 i ∣φ〉, zostały najpierw załadowane do oddzielnych rejestrów kwantowych. Następnie qubit ancilla był inicjalizowany w stanie ∣0〉, aby kontrolować operację zamiany. Na ancilla zastosowano bramkę Hadamarda, aby umieścić ją w superpozycji przed wykonaniem operacji controlled-SWAP. Bramka Fredkin (CSWAP) wykorzystywała ancilla jako kubit sterujący oraz dwa rejestry danych jako cele, co umożliwiało interferencję między stanami. Po tej operacji na ancilla zastosowano drugą bramkę Hadamard, aby zakończyć wzór interferencyjny. Mierzono tylko qubit ancilla, a jego wynik pomiarowy kodował podobieństwo między tymi dwoma stanami. Gdy stany były identyczne, ancilla dawała wynik 0 z prawdopodobieństwem 1, natomiast stany ortogonalne dawały wynik 0 z prawdopodobieństwem 0,5.

Rysunek 2: Ilustracja porównania opartego na prawdopodobieństwie, Jeśli stany ρ i ξ są różne, to obserwowany rozkład prawdopodobieństwa należy do P_E⁻ \ P_E⁺. Proszę kliknąć tutaj, aby zobaczyć większą wersję tej figurki.

Operator gęstości ρ jest powiązany z dowolnym stanem kwantowym ρ ∈ S(H), takim że tr[ρ] = 1, a ρ ≥ 0. Tutaj zbiór wszystkich stanów S(H) układu, który będzie powiązany z przestrzenią Hilberta H. Dodatnia miara operatorowa (POVM) to kwantowy pomiar cech statystycznych, będący zbiorem dodatnich operatorów E₁, . . . , E_n jako E (działającego na H) oraz tożsamości I = . Rozkład prawdopodobieństwa przypisuje pomiar E dla każdego stanu ρ ∈ S(H), gdzie p_j = tr[E_jρ]≥ 0 i = 1²⁶.

4. Porównanie stanów kwantowych oparte na SWAP

Różnicę między dwoma stanami kwantowymi można zmierzyć za pomocą procedury testowej SWAP w obliczeniach kwantowych. Metoda ta została po raz pierwszy wprowadzona przez Barenco i in.²⁷ , a później ponownie odkryty przez Johna Watrousa, Ronalda de Wolfa, Harry'ego Buhrmana i Richarda Cleve'a ²⁸. Test SWAP został zastosowany w obliczeniach kwantowych i uczeniu maszynowym kwantowym ^{15, 29}.

Test SWAP przyjmuje ∣ψ〉 i ∣φ〉 jako stany wejściowe i daje 1 (zmienną losową Bernoulliego) o prawdopodobieństwie 1/2 - 1/2〈φ,ψ〉² , co szacuje kwadrat iloczynu skalarnego obu stanów ³⁰.

Wyjaśnienie obwodu

Rozważmy dwa stany ∣φ〉 i ∣ψ〉 systemu, protokół na początku to ∣0,φ,ψ〉. Po zastosowaniu bramki Hadamarda, stan zmienia się na ∣0,φ,ψ〉 + ∣1,φ,ψ〉. Bramka CSWAP przekształca stan w (0,φ,ψ〉 + ∣1,ψ,φ〉). Po drugiej bramie Hadamarda stan staje się 1/2(|0,φ,ψ〉 + ∣1,φ,ψ〉 + |0,ψ,φ〉 - ∣1,ψ,φ〉)= 1/2∣0〉(|φ,ψ〉 + |ψ,φ〉) + 1/2|1〉(|φ,ψ〉 - |ψ,φ〉). Następnie mierzony jest pierwszy kubit, prawdopodobieństwo uzyskania wyniku 0 wynosi P(Pierwszy kubit = 0) = 1/2 (〈φ|〈ψ| + 〈ψ|〈φ|) 1/2 (|φ,ψ〉 + |ψ,φ〉) = 1/2 + 1/2 |〈ψ|φ〉|². Jeśli ψ i φ są ortogonalne (|〈ψ|ϕ〉|² = 0), to prawdopodobieństwo uzyskania 0 wynosi 1/2. Jeśli stany są identyczne (|〈ψ|ϕ〉|² = 1) to prawdopodobieństwo uzyskania 0 wynosi 1. ²⁴

Rysunek 3: (a) Obwód bramki Fredkina z biegunowym stanem przeciwstawnym, (b) Wyjście wykresu mierzonego prawdopodobieństwem, (c) Obwód bramki Fredkina z bramką Hadamarda, (d) Wyjście wykresu mierzonego prawdopodobieństwem. Proszę kliknąć tutaj, aby zobaczyć większą wersję tej figurki.

Obwód wykorzystywał jeden qubit ancilla wraz z dwoma rejestrami kodującymi stany kwantowe ∣ψ〉 i ∣φ〉. Wszystkie kubity zostały zainicjowane przed rozpoczęciem etapu kodowania. Cechy ekspresji genów były następnie kodowane w odpowiednich rejestrach za pomocą procedury mapowania cech. Do kubitu ancilla zastosowano bramkę Hadamarda, aby utworzyć superpozycję, po czym wykonywano operację controlled-SWAP pomiędzy dwoma rejestrami stanów z ancilla jako kontrolą. Do ancilla zastosowano drugą bramkę Hadamarda, aby uzupełnić wzór interferencyjny, a następnie zmierzono qubit ancilli. Gdy dwa zakodowane stany były identyczne, ancilla konsekwentnie generował wynik 0. Gdy stany były ortogonalne, ancilla dawała wynik z prawdopodobieństwem 0,5. Dla częściowo podobnych stanów prawdopodobieństwo uzyskania 0 wynosiło od 0,5 do 1, co odzwierciedlało stopień podobieństwa między stanami.

5. Estymacja odległości kwantowej

W klasycznej analizie danych odległości między punktami danych można obliczyć bezpośrednio za pomocą miar takich jak odległość euklidesowa czy manhattańska ^2,3. W przypadku kubitów na komputerze kwantowym zadanie to jest bardziej złożone ze względu na probabilistyczny charakter stanów kwantowych. Różnice fazowe i amplitudy prawdopodobieństwa można zmierzyć, ale nie można ich bezpośrednio przedstawić jako odległości między dwoma wektorami ^{24, 26}.

Dla klasterizacji konieczne jest ocenenie względnych pozycji punktów danych względem centroidów klastrów¹³. Aby przypisać każdy kubit odpowiedniemu klastru, należy zdefiniować parametr służący jako wskaźnik bliskości do odpowiedniego centroidu klastra.

Aby to osiągnąć, wprowadza się parametr, który koreluje pozytywnie z podobieństwem, pełniąc tym samym funkcję alternatywy dla konwencjonalnych miar odległości ^15,30.

Proces szacowania odległości rozpoczął się od znormalizowanego stanu kwantowego ∣Ψ〉 oraz kubitu pomocniczego z zerową inicjaturą ∣q₀〉. Celem było oszacowanie odległości między nowym punktem danych zakodowanym w ∣q₁〉 a centroidem klastrowym zakodowanym w ∣q₂〉. Aby przygotować superpozycję wymaganą dla wzorca interferencyjnego, do kubitu ancilla zastosowano bramkę Hadamarda, co dało stan ( ∣0〉 + ∣1〉 ) ⊗ ∣Ψ〉 ). Następnie zastosowano bramkę kontrolowaną SWAP (Fredkin) z ancillą jako kontrolą, która splątała ancillę z dwoma zakodowanymi stanami i umożliwiła ich nakładanie się wpływu na wynik pomiaru. Operacja ta generowała stan ( ∣0〉 ⊗ ∣Ψ〉 + ∣1〉 ⊗_{F swap}(∣Ψ〉)), z którego można było wyodrębnić odległość oparty na iloczynie wewnętrznym poprzez późniejsze pomiary ancilla.

Implementacja i wyjście obwodu

Ten kwantowy układ koduje dane ekspresji genów do kubitów za pomocą kodowania fazowego, a następnie porównuje dwa stany ekspresji genów za pomocą bramki Controlled-Swap (CSwap), znanej również jako Test Swap¹².

Aby stworzyć wymaganą superpozycję, do wszystkich kubitów (q₀ do_{q 4}) stosuje się bramki Hadamarda, co skutkuje równą superpozycją wszystkich stanów bazowych |Ψ〉 = , Ta inicjalizacja umożliwia równoległe obliczenia dla wielu wartości ekspresji genów. Każdy kubit następnie przechodzi rotację fazową, , gdzie θ_x odpowiada odwzorowanej wartości ekspresji genów. Operatory unitarne U(θ,π,π) stosowane do kubitów q_{1-q 4} kodują poziomy ekspresji poszczególnych genów, przy czym każdy kąt θ reprezentuje przekształconą wersję ekspresji genu. Procedura ta mapuje klasyczne dane biologiczne na stany kwantowe poprzez kodowanie fazowe, pozwalając na reprezentację wielu genów w wysokowymiarowej przestrzeni kwantowej⁶.

Bramki CSwap są następnie używane do porównywania zakodowanych stanów poprzez ich splątanie. Kubit pomocniczy q₀ pełni funkcję kontroli, decydując, czy stany q_{1-q 4} są zamieniane. Podobne stany kwantowe generują interferencję konstruktywną w q₀, co skutkuje wyższym prawdopodobieństwem pomiaru ∣0〉. Natomiast stany niepodobności zwiększają prawdopodobieństwo pomiaru ∣1〉. Kolejna bramka Hadamarda na q₀ zapewnia interferencję amplitudy, umożliwiając wydobycie informacji o podobieństwie poprzez pomiar.

Załóżmy, że dwa stany kwantowe ∣ψ〉 i ∣φ〉 reprezentują różne zbiory danych ekspresji genów, |ψ〉 = ∑_ia_i |i〉, |φ〉 = ∑_ib_i |i〉 .

Test Swap ocenia wierność (iloczyn skalny) między nimi:

P (0) = ,

Gdzie ∣〈ψ∣φ〉∣ oznacza iloczyn skalarny. Jeśli P(0) ≈ 1, stany są podobne; jeśli P(0) ≈ 0,5 lub niższa, są one różne.

Takie ramy umożliwiają porównywanie zbiorów danych między pacjentami lub warunkami doświadczalnymi (np. tkanka normalna vs. chora). Zapewnia efektywną podstawę do klastrowania danych o wysokim wymiarze w modelach kwantowego uczenia maszynowego. Test Swap wspiera identyfikację podobieństw między stanami kwantowymi, co może być wykorzystane do grupowania próbek w znaczące klastry⁴.

Rysunek 4: Obwód pomiaru odległości między punktami danych a ogniskami. Proszę kliknąć tutaj, aby zobaczyć większą wersję tej figurki.

Rysunek 5: Wynik wykresu mierzonego prawdopodobieństwem. Proszę kliknąć tutaj, aby zobaczyć większą wersję tej figurki.

Punkt danych był najpierw kodowany do stanu kwantowego ∣ψ〉, a odpowiadający mu środek skupiska kodowano do stanu ∣φ〉. Następnie wykonano wcześniej procedurę testu zamiany, aby porównać te dwa stany, a prawdopodobieństwo pomiaru ancilla P(0) zostało zarejestrowane. Wierność między stanami uzyskano jako F=∣〈ψ∣φ〉∣², a odległość kwantowa została zdefiniowana jako D (ψ,φ) = . Mniejsza wartość D wskazywała, że punkt danych znajduje się bliżej centroidu w przestrzeni cech kwantowych.

6. Początkowy wybór centroidu

Inicjalizacja centroidów klastrowych jest kluczowa dla stabilności i dokładności klastrowania K-Means. Losowa selekcja może powodować słabo rozłożone centroidy, co prowadzi do wolnej zbieżności i wyników suboptymalnych. Aby rozwiązać ten problem, stosuje się metodę proporcjonalnej odległości prawdopodobieństwa inspirowaną strategią K-Means++²⁰ . W podejściu wzmocnionym kwantowo odległości są oceniane za pomocą Quantum Distance Estymator oparty na teście SWAP, co zapewnia, że wybrane centroidy lepiej odzwierciedlają rozkład danych bazowych. Ta strategia zwiększa rozdzielanie klastrów i poprawia odporność algorytmiczną, szczególnie w zbiorach danych o wysokich wymiarach.

Proces inicjalizacji centroidu rozpoczął się od losowego wyboru jednego punktu danych, który miał służyć jako pierwszy centroid. Odległość kwantowa między tym centroidem a każdym pozostałym punktem danych była następnie obliczana za pomocą procedury szacowania odległości kwantowej. Na podstawie tych wartości odległości utworzono rozkład prawdopodobieństwa, w którym każdemu punktowi przypisano prawdopodobieństwo wyboru proporcjonalne do kwadratu odległości od najbliższego środka ciężkości. Nowe centroidy były próbkowane według tego rozkładu, a procedurę powtarzano aż do uzyskania pożądanej liczby centroidów K. To podejście dało początkowy zbiór centroidów o znacznie lepszej separacji niż losowy dobór.

7. Obliczanie wariancji kwantowej

Wariancja klastrów ilościowo określa zwartość punktów danych wokół ich centroidów, co czyni ją kluczową miarą do oceny jakości klasteryzacji. W klasycznych średnich K-wariancja oblicza się jako średnią kwadratową odległość między punktami danych a ich przypisanymi centroidami. W podejściu wzmocnionym kwantowo odległości te są uzyskiwane za pomocą Quantum Distance Estymator (za pomocą testu SWAP), który oblicza podobieństwa między stanami kwantowymi oparte na wierności. Sumując kwadrat odległości w obrębie każdego klastra i normalizując przez jego wielkość, otrzymujemy wartość wariancji odzwierciedlającą stopień spójności wewnątrz klastra. Minimalizowanie tej zmienności zapewnia bardziej zwarte i znaczące skupiska, co jest szczególnie ważne w wysokowymiarowych zbiorach danych o ekspresji genów do rozróżniania próbek nowotworowych i nienowotworowych.

Przypisanie klastrów przeprowadzono poprzez przypisanie każdego zakodowanego punktu danych kwantowych do najbliższego centroidu za pomocą kwantowej estymacji odległości. Dla każdego klastra C_k obliczono odległość kwantową D(ψ i,C_k) między każdym punktem danych a jego centroidem. Wariancja wewnątrzklastrowa została następnie obliczona za pomocą , które mierzyły zwartość każdego klastra. Całkowita wariancja została uzyskana przez sumowanie poszczególnych wariancji we wszystkich klastrach. Ta całkowita wartość wariancji była rejestrowana w celu określenia optymalnej liczby klastrów oraz oceny ogólnej wydajności klastrowania.

8. Optymalizacja oparta na gradientach kwantowych

Określenie optymalnej liczby klastrów (K) jest fundamentalnym wyzwaniem w zadaniach klastrowania. Tradycyjne K-Means wymagają predefiniowania K , co często prowadzi do niedo- lub nadmiernego skupienia. W naszym podejściu wspieranym kwantowo integrujemy optymalizację opartą na gradientach kwantowych (QGBO), aby adaptacyjnie zidentyfikować optymalną liczbę klastrów. Algorytm iteracyjnie zwiększa K, ponownie oblicza wariancję na każdym kroku i ocenia redukcję wariancji (ΔV). Gdy poprawy wariancji spadną poniżej progu, klasteryzacja zostaje zakończona. Gradient kwantowy oblicza się za pomocą reguły przesunięcia parametrów, która szacuje pochodne wartości oczekiwanych z układów kwantowych. Takie podejście zapewnia, że ostateczna liczba klastrów równoważy dokładność i efektywność, co czyni je szczególnie przydatnym w zastosowaniach bioinformatycznych, gdzie rzeczywista liczba podtypów biologicznych nie jest znana z góry.

Proces klastrowania rozpoczął się od K=1, a całkowita wariancja V(K) była obliczana za pomocą procedury obliczeń wariancji kwantowej. Liczba klastrów została następnie zwiększona do K+1, a wariancja V(K+1) została ponownie obliczona. Zmniejszenie wariancji, ΔV=V(K)−V(K+1), zostało ocenione, aby ustalić, czy dodatkowe klastry nadal poprawiają zwartość danych. Iteracja zatrzymała się, gdy ΔV spadło poniżej ustalonego progu, co wskazuje, że dalsze wzrosty K nie przyniosły istotnych popraw. Skonstruowano parametryzowany obwód kwantowy z bramkami wariacyjnymi do monitorowania zmian krzywizny trendu wariancji, a te informacje kierowały procesem optymalizacji klastra. Optymalna liczba klastrów została wybrana jako wartość K , przy której ustabilizowała się redukcja wariancji, co skutkowało zwartymi i dobrze rozdzielonymi klastrami.

9. Obliczanie wariancji klastrów i przechowywanie w_liście V

Po utworzeniu stabilnych klastrów algorytm oblicza wariancję klastrów, aby zmierzyć zwartość każdego klastra. Wariancja V_kj dla danego klastra jest wyznaczana na podstawie odległości między każdym punktem danych w klastrze a centroidem klastra:

gdzie: x oznacza próbkę ekspresji genów, C_i to klaster, C_ci to środek ognia klastra C_i, V_kj to wariancja zarejestrowana dla j iteracji z k klastrami.

Ta wariancja jest przechowywana w _liście V, która później posłuży do określenia optymalnej liczby klastrów.

10. Określenie optymalnej liczby klastrów

Aby znaleźć optymalną liczbę klastrów K, algorytm wykonuje wiele iteracji, obserwując różne warunki początkowe. Kluczowe kroki obejmują:

Algorytm najpierw zidentyfikował wartość minimalnej wariancji z listy wariancji obliczonych dla różnych wartości K. Redukcję wariancji między kolejnymi liczbami klastrów zmierzono następnie za pomocą wyrażenia ΔV=∣V_{k−V k−1}∣, gdzie V_k oznaczało wariancję dla K klastrów, a V_k−1 dla klatrów K−1. Jeśli redukcja ΔV spadła poniżej ustalonego progu, co wskazuje na znikomą poprawę klastrowania, procedura została zakończona. W przeciwnym razie liczba klastrów była zwiększana, a obliczenia powtarzano aż do osiągnięcia optymalnej liczby klastrów.

11. Finalizacja klastrów dla klasyfikacji nowotworowych i nienowotworowych

Po ustaleniu optymalnej liczby klastrów K , ostateczny zestaw klastrów reprezentuje odrębne grupy w danych ekspresji genów. Zazwyczaj algorytm generuje dwa główne klastry:

Jeden klaster reprezentujący komórki nowotworowe (oznaczone wyraźnymi sygnaturami ekspresji genów związanych z nowotworem).

Jeden klaster reprezentuje komórki nienowotworowe (zawierające prawidłowe profile ekspresji genów).

Parametry, zmienne i stałe stosowane w proponowanym algorytmie klastrowania K-Means kwantowego są wymienione w Tabeli 1. Definiuj wymiary zbioru danych, ustaw liczbę klastrów K oraz stosuj kryteria zatrzymania i progi optymalizacji do kierowania procesem. Konfiguruj ustawienia obliczeniowe, takie jak liczba strzałów na jeden przebieg i losowe seedy, aby zapewnić powtarzalność. Inicjalizuj środki ciężkości metodą selekcji opartej na prawdopodobieństwie i aktualizuj je iteracyjnie aż do zbieżności. Tabela określa również oczekiwane wyniki, w tym etykiety klastrów, centroidy, optymalne K, metryki ewaluacyjne oraz wykresy wizualizacyjne.

Kategoria	Parametr	Wartość / Domyślność	Przypisy
Zbiór danych	Zbiór danych dotyczących raka piersi	569 próbek × 32 cechy (zmniejszone do 2 komponentów PCA)	Zredukowana wymiarowość z PCA
Liczba klastrów	K	Dynamiczne, początkowo 1, do 5	Optymalizacja za pomocą redukcji wariancji
Maksymalne skupiska	Kmax	5	Górna granica wyszukiwania
Liczba uderzeń na punkt	N	1024	Pomiary na wykonanie obwodu
Zatrzymanie tolerancji	ε	1 × 10^-14	Kryterium zbieżności wariancji
Próg nachylenia wariancji	ΔV	9.9 × 10^-4	Próg zatrzymania dla optymalizacji
Obserwacje	Mobsrv	3	Niezależne uruchomienia na wielkość klastra
Limit iteracji	–	10	Maksymalne kroki aktualizacji centroidów na przebieg
Losowe ziarno	–	42	Zapewnia powtarzalność
Oczekiwane wyniki	–	Etykiety klastrów, centroidy, optymalne K, metryki ewaluacji, wykresy	Eksportowane jako pliki .csv i .png
Wariancje między klastrami	Vlist	pusty	Wykrywa optymalną K
Centroid j	CJ	inicjalizowane przez funkcję (na podstawie prawdopodobieństw proporcjonalnych do kwadratu odległości punktów)	Aktualizowane iteracyjne i przechowywane ostateczne centroidy

Tabela 1: Materiały, oprogramowanie i ustawienia powtarzalności

Krok	Funkcja / API (z twojego kodu)	Działania	Oczekiwany rezultat
Kodowanie cech	qc.u(theta, pi, pi, qubit)	Zakoduj znormalizowaną cechę klasyczną do rotacji kubitu	Stan kubitu
Test SWAP / odległość kwantowa	get_Distance(x, y) za pomocą qc.cswap()	Buduj układ 3-kubitowy (ancilla + dwa stany)	Identyczne → P(0) ≈ 1.0; ortogonalna → P(0) ≈ 0,5
Wykonywanie obwodów	SamplerV2 z AerSimulator (1024 zdjęcia)	Uruchom układ na symulatorze z transpilacją (poziom opt 1)	Rozkład prawdopodobieństwa dla kubitu ancilla
Inicjalizacja centroidów	initialize_centroids_kmeans_pp(punkty, k)	Wybierz początkowe środki ciężkości proporcjonalne do odległości	Różnorodne centroidy początkowe
Przypisanie klastrów	find_nearest_neighbour(punkty, centroidy)	Przypisz punkty do najbliższego środka ciężkości	Stabilne przynależności do klastrów
Obliczenie wariancji	calculate_variance(w centrum, centers_distance)	Oblicz wariancję wewnątrzklastrową	Wariancja maleje z każdą iteracją
Nachylenie wariancji	grad_slope(k, V_k, k-1, V_k-1)	Porównaj ΔV z ε = 1e-14 oraz progiem nachylenia ΔV ≤ 0,000099	Wykryte optymalne K
Wizualizacja	matplotlib.pyplot, plot_histogram	Przypisania klastrów wykresów i wyniki kwantowe	Wykresy rozrzutowe PCA, wykresy wariancji, histogramy
Obliczenia metryczne	silhouette_score, calinski_harabasz_score, davies_bouldin_score	Ocena jakości klastrowania	Sylwetka ≈ 0,64, CH ≈ 766, DB ≈ 0,65

Tabela 2: Szczegóły implementacji proponowanego algorytmu do uruchomienia.

Implementacja i algorytmy

Algorytm K-Means Kwant z Optymalnym Określaniem Klastrów to metoda klasteryzacji wspomaganej kwantowo, która dynamicznie identyfikuje optymalną liczbę klastrów przy jednoczesnym wykorzystaniu mapowania cech^{kwantowych 19} . Procedura rozpoczyna się od rozważenia wszystkich punktów danych jako należących do jednego klastra. Liczba klastrów K jest stopniowo zwiększana. Centra klastrów są inicjalizowane probabilistycznie według odległości między punktami, po czym każdy punkt danych jest przypisywany do najbliższego środka ciężkości, tworząc K klastrów. Następnie obliczana jest wariancja klastrów, a środki ciężkości są aktualizowane. Proces ponownego przypisywania powtarza się iteracyjnie, aż nie następują dalsze zmiany.

Algorytm ocenia wariancję w wielu iteracjach, zapisując wartości wariancji odpowiadające różnej liczbie klastrów. Wartość optymalną K określa się poprzez minimalizację wariancji podczas monitorowania redukcji wariancji ΔV. Jeśli ΔV stanie się znikome mały, procedura zostaje zakończona; w przeciwnym razie K jest zwiększane i proces klastrowania rozpoczyna się od nowa. Ta adaptacyjna strategia zapewnia efektywne i dokładne podziały danych, szczególnie w wysokowymiarowych przestrzeniach cech.

Rysunek 6: Schemat blokowy proponowanej procedury Hybrid Quantum K-Means Clustering, pokazujący mapowanie cech kwantowych, inicjalizację centroidów, iteracyjne przypisywanie klastrów, obliczenia wariancji, sprawdzanie zbieżności oparte na wariancji oraz selekcję optymalnej liczby klastrów wspomaganą gradientem kwantowym. Proszę kliknąć tutaj, aby zobaczyć większą wersję tej figurki.

Poniższe kroki przedstawiają algorytm Kwant K-Means do klasteryzacji danych o ekspresji genów nowotworowych i nienowotworowych.

Algorytm: Klasteryzacja danych ekspresji genów komórek nowotworowych i nienowotworowych za pomocą algorytmu kwantowych k-means

Krok 1: Mapowanie cech kwantowych (kodowanie wielofunkcyjne).
Krok 2: Zakładając, że początkowo wszystkie punkty danych należą do tego samego klastra, ustaw wartość K=1 (gdzie K: to liczba optymalnych klastrów, V: to wariancja klastra, a ΔV: redukcja wariancji).
Krok 3: Inicjalizacja Centrów (Wybieranie początkowych punktów centralnych na podstawie proporcji prawdopodobieństwa odległości między punktami danych).
Krok 4: Przypisz każdy punkt danych do jego najbliższego środka ciężkości, co utworzy zdefiniowane klastry 'K'.
Krok 5: Oblicz wariancję klastrów i umieść nowy środek ciężkości każdego klastra.
Krok 6: Powtórz Krok 4, czyli przypisz każdy punkt danych do nowego, najbliższego centroidu każdego skupiska.
Krok 7: Jeśli nastąpi jakaś zmiana, przejdź do Kroku 5, a potem do Kroku 8.
Krok 8: Teraz otrzymujemy klaster C_j ("j'-ta iteracja z 'k' numerem klastrów) i obliczamy wariancję V_kj= , gdzie 'x': punkt danych należy do klastra C_i, a C_ci: centrum klastra klastra C_i. Prowadź zapis wariancji V_kj na _liście V i zaczynaj od nowa klasteryzować z nowymi centrami od kroku 3 (kilka razy, czyli 'j', gdzie 1 ≤ j ≤ M_obsrv) z tym samym 'K'.
Krok 9: Znajdź minimalną wariancję V z_listy V z 'K' numerem klastrów.
Krok 10: Oblicz ΔV (ΔV = |V_k - V_k-1|, gdzie V_k: to wariancja z 'K' nielicznymi klastrami i V_k-1: to wariancja z 'K-1' bez klastrów), jeśli ΔV jest zoptymalizowany na poziomie kwantowym (ogromna redukcja), to ZAKOŃCZ, w przeciwnym razie zwiększaj K (K=K+1) i przejdź do kroku 3 z nowym 'K'.
Krok 11: Klastry są gotowe, a optymalna liczba klastrów to 'K'.

Algorytm mapowania cech kwantowych

Algorytm 1: Mapowanie cech kwantowych

Wejścia: P wskazuje każdy ze stanów kwantowych |ψ〉 i |Φ〉
Efekt: Estymacja | 〈 ψ | Φ〉 |²
Kroki algorytmu:
Krok 1: Bierzemy kubit i inicjujemy go przez zero; zastosuj bramkę Hadamarda i obróć ją z bazy Z do osi X.
Step 2: Ustawiamy φ (0 ≤ φ ≤ π ) w radianie zgodnie z wartością punktu danych względem cechy 1.
φ = 2*rad(^cos-1)(d₀)), gdzie d₀ oznacza wartości danych cech 1, a d₀ ∈ [0, 1].
Krok 3: Ustawiamy θ (0 ≤ θ ≤ π ) w radiannie zgodnie z wartością punktu danych względem cechy 2.
θ = 2 * rad(^cos-1(d₁)), gdzie d₁ oznacza wartości danych cech 2, a d₁ ∈ [0, 1].
Krok 4: Używamy bramki kwantowej U3 do implementacji rotacji i kodowania cech punktów danych.

To obraca kubit o Φ o promieni względem osi dodatniej x oraz θ o promień względem dodatniej osi z.

Porównanie algorytmu stanów kwantowych

Algorytm 2: Porównanie stanów kwantowych

Dane wejściowe: Dwa kubity |q₁〉 i |q₂〉 każdy ze stanów kwantowych |ψ〉 i |Φ〉
Efekt: Estymacja | 〈ψ|Φ〉 |²
Kroki algorytmu:
Krok 1: Rozważenie kubitu A jako ancilla i inicjalizacja go według stanu |0〉
Krok 2: Zastosuj bramkę Hadamarda na kubitie A
Krok 3: Zastosuj CSWAP na kubitach |q₁ 〉 i |q₂ 〉 (w stanie|ψ〉 i |Φ〉), gdzie A jest kubitem sterującym
Krok 4: Zastosuj bramkę Hadamarda na kubitie A
Krok 5: Zmierz A w na podstawie Z i zapisz wynik pomiaru jako M
powrót M jako nasze oszacowanie | 〈 ψ|Φ 〉 |²

Algorytm szacowania odległości kwantowej dla k-średnich klasterów

Algorytm 3: Estymator odległości kwantowej i wybierz nowy centroid klastrów

Wejścia: P zero punktów danych i K zero centroidów klastrowych, każdy ze stanów kwantowych |ψ〉 i |Φ〉
Efekt: Nowy skupiony środek ciężkości związany z punktami danych
Kroki algorytmu:
dla i w zakresie od 1 do P:
Wybierz i punkt danych i zapisz go na |q_i 〉
dla j w zakresie od 1 do K:
Wybierz j^sklastrowany środek i ustaw go na |q_j 〉
Porównaj stany kwantowe |q_i 〉 oraz |q_j 〉 tzn. i^- kubit z^j-tym centroidem i zapisz pomiar w M jako (M_{, i}, j)
koniec dla
Znajdź minimalną odległość (M_min ,min) od M, a zbiór min to nowy środek ogniska |q_i 〉 i zapisz go jako C_i
koniec dla
powrót C jako nasza nowa lista centroidów

M= lista wszystkich skupistych odległości centroidalnych od |q_i 〉 kubita i-tego
C = lista wszystkich nowo obliczonych skupień o minimalnych odległościach skupionych C_i z |q_i 〉; ∀_{(i∈{1,...,P})}

Algorytm wyboru początkowego środka ciężkości

Algorytm 4: Oblicz początkowe punkty ciężkości, używając proporcji prawdopodobieństwa odległości między punktami danych

Wejścia: m liczba punktów danych (X₁, X₂,...,X_m), każdy ze stanów kwantowych |ψ〉 i |Φ〉
Wyjście: zwróć zbiór S o K początkowych centroidach
Kroki algorytmu:
Krok 1: Wybierz losowo jeden punkt X z punktów danych X_i (1 ≤ i ≤ m) i dodaj go do zbioru S
Krok 2: Dla każdego X_i oblicz odległość między X_i za pomocą Quantum Distance Estymator a najbliższym punktem centroidalnym w S i ustaw odległość jako D_dist(X_i)
Krok 3: Wybierz liczbę Y równomiernie między 0 a D_dist(X₁)² + D_dyst (X₂)² + ...+ D_dyst (X_m)²
Krok 4: Znajdź unikalną liczbę całkowitą i taką, że
D_dystynkt (X₁)² + D_dyst (X₂)² + ...+ D_dyst (X_i)² >= Y > D_dyst (X₁)² + D_dyst (X₂)² + ...+ D_dyst (X_i-1)²
Krok 5: Dodaj X_i do S
Krok 6: Dopóki nie zostanie znalezione K centroidów, powtarzaj kroki 2–4

powrót S jako początkowe punkty ciężkości

Algorytm obliczania wariancji kwantowej

Algorytm 5: Obliczanie wariancji kwantowej

Dane wejściowe: P liczba punktów danych, każdy ze stanów kwantowych | ψ〉 i |Φ〉
Wynik: zwróć wariancję punktów danych
Kroki algorytmu:
totalVariance ← 0
dla i w zakresie od 1 do K:
Wybierz i^th skupiony środek i ustaw go na |q_i 〉
totalVariancei ← 0, M ← 0
dla wszystkich j ∈ P, związany z centroidem klastrowym i:
Wybierz j punkt danych i ustaw go na |q_j 〉
Porównaj stany kwantowe |q_i 〉 oraz |q_j 〉 t. tj^{. i -} tego środka ciężkości z^j-tym punktem danych i zapisz pomiar w M_j
M ← M + Mj
koniec dla
totalVariance_i ← [C_i to^i-ty klaster; |C_i | nie jest żadnym z punktów danych w^i-tym klastrze, D_k to punkt danych ∈ C_i i M_k
to odległość między centroidem C_i a D_k]
totalVariance ← totalVariance + totalVariancei
koniec dla
wróć totalVariance

Algorytm optymalizacji oparty na gradientach kwantowych (uzyskanie optymalnej liczby klastrów)

Etap optymalizacji oparty na gradientach kwantowych określa optymalną liczbę klastrów poprzez monitorowanie zmiany wariancji wewnątrzklastrowej wraz ze wzrostem K. Oblicz wariancję dla kolejnych wartości K i wymień zmianę między nimi. Gdy redukcja wariancji spada poniżej ustalonego progu, dodatkowe klastry przestają poprawiać zwartość, a odpowiadające mu K jest wybierane jako optymalne. To kryterium oparte na krzywiźnie zapewnia, że klasteryzacja kończy się w miejscu, gdzie naturalna struktura danych zostaje uchwycona bez nadmiernego podziału.

Algorytm 6: Optymalizacja oparta na gradientach kwantowych

Dane wejściowe:
Parametryzowany układ kwantowy QC(θ) z pojedynczą bramką obrotową kubitu R_Y(θ).
Kwantowa obserwable = Z (wartość oczekiwana Pauli-Z).
Zakres wartości parametrów θ.
Efekt: Druga pochodna f′′(θ) wartości oczekiwanej 〈Z〉 względem θ.
Kroki algorytmu:
Krok 1: Zainicjalizuj układ kwantowy QC(θ) o pojedynczym kubicie:
Parametryzowana bramka rotacji R_Y(θ).
Pomiar w oparciu obliczeniowym (Z).
Krok 2: Zdefiniuj funkcję Evaluate_ Oczekiwanie(θ), czyli f′(θ) =
Przypisz parametr θ do układu.
Wykonaj układ na symulatorze kwantowym z N shotami.
Mierz prawdopodobieństwa wyniku P(0) i P(1).
Oblicz wartość oczekiwaną:
f(θ)=P(0)−P(1)
Krok 3: Oblicz drugą pochodną za pomocą reguły przesunięcia parametrów:
Ustaw wartość przesunięcia s =
Oblicz wartości oczekiwane w przesuniętych punktach:
f(θ+s), f(θ), f(θ−s)
Oblicz drugą pochodną:
f ′′(θ) =
Krok 4: f ′′(θ) do analizy zachowań redukcji wariancji.

Szczegóły implementacji proponowanego podejścia do klastrowania kwantowego przedstawiono w Tabeli 2. Tabela określa funkcje możliwe do uruchomienia oraz API używane na każdym etapie algorytmu, w tym kodowanie cech w obwodach kwantowych, wykonanie testu SWAP dla szacowania odległości, inicjalizację centroidów, iteracyjne przypisanie klastrów oraz ocenę wariancji/ΔV. Wymienione są także parametry wykonania układów, takie jak użycie SamplerV2 z backendem AerSimulator przy 1024 strzałach oraz optymalizacja transpilacji poziomu 1. Ponadto tabela przedstawia metody wizualizacji stosowane do generowania wykresów rozrzutowych PCA, wykresów wariancji i histogramów, a także metryki oceny klasteryzacji (silhouette_score, calinski_harabasz_score i davies_bouldin_score). Poprzez szczegółowe opisanie konkretnych funkcji i API na poziomie poleceń, tabela zapewnia powtarzalność wszystkich kroków obliczeniowych w proponowanym algorytmie.

Wyniki

Dobry klaster zależy od różnych czynników, takich jak odległość między klastrami, odległość w obrębie klastra, kryterium współczynnika wariancji itd. Dlatego wyniki klastrowania oceniano za pomocą trzech standardowych wskaźników: Silhouette Score, Calinski-Harabasz Index (CH Index) oraz Davies-Bouldin Index (DB Index). Silhouette Score mierzy rozdzielenie między klastrami jako ,

Dyskusja

Niniejsze badanie proponuje nowatorski hybrydowy algorytm klastrowania kwantowego K-Means z optymalnym wykrywaniem klastrów, specjalnie zaprojektowany do klasyfikacji próbek nowotworowych i nienowotworowych na podstawie danych o ekspresji genów o wysokich wymiarach. Podejście to integruje mapowanie kwantowe wielofunkcyjne, estymację odległości kwantowej opartą na teście swap oraz optymalizację opartą na gradientach kwantowych, aby dynamicznie określić optymalną liczbę klastrów. W przeciwieństwie do trady...

Materiały

Lista materiałów użytych w tym artykule

Nazwa	Firma	Numer katalogowy	Komentarze
Apple MacBook Pro (chip M1)	Apple Inc.	-	8?rdzeniowy procesor / 8?rdzeniowy GPU, 16? GB zunifikowanej pamięci — Wykorzystywane do symulacji lokalnej
Zestaw danych ekspresji genów raka piersi	Kaggle	-	Zbiór danych zawierający 569 próbek, 32 cechy (zmniejszone przez PCA w badaniu)
macOS Monterey (system operacyjny)	Apple Inc.	12.6.9	Środowisko wykonawcze używane na maszynie lokalnej
matematyka (standardowa biblioteka Pythona)	Python Software Foundation	Wbudowane	Podstawowe funkcje matematyczne
Matplotlib	Społeczność Matplotlib	3.8.4	Wykresy i wizualizacja
NoiseModel, QuantumError, ReadoutError (Qiskit Aer)	Projekt IBM / Qiskit	część Aer 0.13.3	Wykorzystywane do symulacji realistycznego szumu kwantowego
NumPy	Deweloperzy NumPy	1.26.4	Operacje numeryczne i manipulacja tablicami
Pandy	Zespół rozwojowy Pandas	2.2.2	Obsługa danych, I/O, operacje tabelaryczne
Python	Python Software Foundation	3.10.12	Język programowania używany w środowisku Jupyter / IPython
Qiskit Aer	Projekt IBM / Qiskit	0.13.3	Backend symulatora, z modelowaniem i wykonywaniem szumów
Qiskit IBM Runtime – Session, SamplerV2	Projekt IBM / Qiskit	0.41.1	Ramy wykonawcze dla obwodów w symulatorze
Qiskit Terra	Projekt IBM / Qiskit	0.45.0	Kwantowe ramy do konstrukcji i transpilacji układów
scikit-learn	Programiści scikit-learn	1.4.2	PCA, metryki klastrowania, wstępne przetwarzanie danych