Do czasu misji New Horizons planetę karłowatą Pluton wyobrażaliśmy sobie, poniekąd słusznie, jako glob pogrążony w ciemnościach, zimny i praktycznie martwy...

Grudzień odznacza się najdłuższymi nocami w ciągu roku, stąd mogłoby się wydawać, że właśnie w grudniu miłośnicy astronomii mają najwięcej okazji do przyglądania się ciałom niebieskim. Niestety, grudniowe noce bardzo często są zachmurzone lub zamglone i w rezultacie liczba godzin, którą można poświęcić na obserwacje, nie jest taka duża...

Liga zadaniowa Wydziału Matematyki, Informatyki i Mechaniki, Wydziału Fizyki Uniwersytetu Warszawskiego i Redakcji Delty

Wyplatanie było ważnym osiągnięciem technologicznym, dzięki któremu tworzono powrozy, koszyki, łapcie, płoty, tkaniny itp. Z drugiej strony czynność ta nie zawsze była poważana, o czym świadczy powiedzenie "pleść trzy po trzy".

Grawitacja jest jednym z czterech podstawowych oddziaływań znanych fizykom. Mimo że doświadczamy jej w codziennym życiu, jej natura jest najsłabiej zbadana zwłaszcza w warunkach odbiegających od ziemskich. Obserwacje Kosmosu pozwalają nam na śledzenie procesów zachodzących w ogromnych, nieosiągalnych na Ziemi polach grawitacyjnych, i w ten sposób testować nasze teorie. Jak do tej pory świetnie sprawdza się ogólna teoria względności Einsteina: opis sposobu, w jaki masy zakrzywiają wokół siebie przestrzeń i zmieniają tempo, w jakim płynie czas. Jeśli masy poruszają się w czasoprzestrzeni z przyśpieszeniem, to faluje ona i drga proporcjonalnie do wielkości mas i szybkości ich ruchu. Zmienne w czasie zachowanie się odległości i przepływu czasu w czasoprzestrzeni, wywołane ruchem mas, nazywamy falami grawitacyjnymi.

Zastanówmy się nad następującym pytaniem: czym jest komputer? Sądzę, że odpowiedź na tak zadane pytanie może zależeć w znacznej mierze od tego, kogo o to pytamy. Taka sytuacja nie jest, oczywiście, czymś wyjątkowym. Jeśli zamiast informatyką zajmiemy się cukiernictwem i zapytamy: czym jest tort, to też różne osoby będą różnie odpowiadać...

"Informacja jest fizyczna" powiedział Rolf Landauer, fizyk, któremu zawdzięczamy zrozumienie faktu, że usunięcie 1 bitu informacji z pamięci komputera wiąże się z nieuniknionym wytworzeniem ciepła o wartości gdzie jest temperaturą otoczenia, a stałą Boltzmanna. Był to wynik, który pokazał, że warto myśleć o fizycznych podstawach przetwarzanej przez nas informacji, aby zrozumieć ograniczenia i perspektywy dalszego rozwoju komputerów. Dziś wiemy, że materia na poziomie mikroskopowym opisywana jest przez prawa fizyki kwantowej...

W 1994 roku Peter Shor, pracujący wówczas w Bell Labs w New Jersey, pokazał, jak przy użyciu hipotetycznego komputera kwantowego rozłożyć w czasie wielomianowym dowolną liczbę naturalną na czynniki pierwsze. W tamtym czasie algorytmy kwantowe dopiero raczkowały. To właśnie odkrycie Shora spowodowało wielki rozwój tej dziedziny. Społeczność informatyków zrozumiała, że gdyby udało się zbudować komputer kwantowy rozsądnej wielkości, to świat stałby się istotnie inny. Nie jest bowiem znany żaden algorytm dla problemu faktoryzacji, czyli rozkładu na dzielniki pierwsze, który działa w czasie wielomianowym na komputerze klasycznym. Co więcej, nawet nie znaleziono algorytmu losowego, który z dużym prawdopodobieństwem w zazwyczaj niedługim czasie faktoryzuje liczbę: nie jest po prostu znana zupełnie żadna rozsądna heurystyka...

Wydaje się, że moc, szybkość obliczeniowa współczesnych komputerów, bazujących na krzemie, osiąga swoje plateau wynikłe z ograniczeń natury materiałowej. Jednocześnie w wielu dziedzinach życia codziennego, poczynając od prób unikania korków w planowanej podróży, poprzez minimalizację kosztochłonności produkcji aż po liczne zaawansowane zagadnienia badawcze z zakresu teorii sterowania, staramy się optymalizować nasze postępowanie. Wobec wspomnianych ograniczeń sprzętowych pozostaje nam poszukiwanie nowych algorytmów dla optymalizacji lub zupełnie nowych paradygmatów obliczeniowych - być może kwantowych?

W tym miesiącu omówimy zadanie Liczby, które pojawiło się podczas rundy 72. na portalu codeforces.com.

Czasem warto przetłumaczyć problem na inny język, aby łatwiej go rozwiązać.

Liga zadaniowa Wydziału Matematyki, Informatyki i Mechaniki, Wydziału Fizyki Uniwersytetu Warszawskiego i Redakcji Delty

Jeżeli określimy dodawanie i mnożenie punktów płaszczyzny, z wyróżnionymi punktami 0 i 1, w sposób przedstawiony na rysunku, to otrzymamy liczby zespolone...

W poniższym artykule postaramy się przybliżyć Czytelnikowi niektóre podstawowe pojęcia algebry wieloliniowej nad liczbami zespolonymi, która jest podstawą rozważań w kwantowej teorii obliczeń. Bez zbędnej zwłoki przystąpimy od razu do konkretów.

Jak można dowiedzieć się z rozlicznych filmów akcji, nieodłączną częścią życia każdego szanującego się tajnego agenta jest wymiana tajnych informacji, najlepiej takich z wielką, czerwoną pieczęcią "Top Secret". Jeśli agent ma taką możliwość, najlepiej przekazać teczkę pełną tajemnic osobiście, jednak jest to luksus, na który może on pozwolić sobie w niewielu sytuacjach, gdyż nierzadko odbiorca tych tajemnic znajduje się na drugim końcu globu. W tej sytuacji konieczne staje się odpowiednie zaszyfrowanie naszych sekretów, aby nawet w przypadku przechwycenia ich przez oślizgłe macki szwarccharakterów, pozostały one sekretami.

Jednym z ważniejszych osiągnięć informatyki opartej o komputer kwantowy, które zresztą eksponujemy w tym numerze Delty, jest opracowanie efektywnego (wielomianowego od rozmiaru danych) algorytmu na rozkład dużych liczb na czynniki pierwsze. Wspaniały, budzący zachwyt wynik. Nie dość, że przepiękny, korzystający z bardzo ładnego fragmentu matematyki, to jeszcze pozwalający wierzyć, że komputer kwantowy złożony z kubitów jest istotnie lepszy od komputera klasycznego, zawierającego pamięć o bitach. Albo inaczej: że (też prezentowany w tym numerze) model obliczeń komputera kwantowego ma istotnie większą siłę wyrazu (przy założeniu wielomianowego czasu działania) niż klasyczny model Turinga czy inne równoważne.