AQUA@home, Экспериментальное изучение Адиабатического КВантового Алгоритма Налаштування

[nikelong]

Проект "AQUA@home"

----------------------------------------------------------------------------------------------------------

• Официальный сайт
• Официальная статистика по команде "Ukraine"
• Статус серверов проекта
• Стат на фришниках
• Стат команды на фришниках

----------------------------------------------------------------------------------------------------------
ТОП-20 участников:

----------------------------------------------------------------------------------------------------------
Дата основания команды - 14.12.2008 Капитан - Death
----------------------------------------------------------------------------------------------------------
Для присоединения к команде Украины:
1. Загрузите BOINC менеджер (Если его у Вас еще нет!)
2. Перейдите в "расширенный вид"
3. Выберите сервис ---> добавить проект
4. Введите адрес проекта http://aqua.dwavesys.com/
5. Введите свои регистрационные данные.
6. Найдите нашу команду. Она называется Ukraine и адрес ее статистики вы могли видеть выше.
7. Если есть доступные для загрузки задания Вы их получите и начнете расчеты.
----------------------------------------------------------------------------------------------------------
Полезная информация:
Для идентификации пользователя в BOINC могут служить 2 вещи:
1) пара e-mail/пароль
2) межпроектный идентификационный ID (Cross-project ID) - 32значное шестнадцатиричное число.

Если Вы пожелаете подключится ещё и к другому BOINC-проекту, то помните: чтобы не плодить новых аккаунтов при подключении к новому проекту или команде, нужно обязательно везде регистрироваться с одним и тем же e-mail/паролем либо CPID. если при регистрации в проекте указать другие e-mail или пароль, BOINC создаст новый аккаунт с тем же именем!
----------------------------------------------------------------------------------------------------------


О проекте:

D-Wave's AQUA (Adiabatic QUantum Algorithms) is a research project whose goal is to predict the performance of superconducting adiabatic quantum computers on a variety of hard problems arising in fields ranging from materials science to machine learning. AQUA@home uses Internet-connected computers to help design and analyze quantum computing algorithms, using Quantum Monte Carlo techniques.

AQUA@home is based at D-Wave Systems Inc., Burnaby, British Columbia, Canada.

Что они считают, решая уравнение Фокера-Планка, не знаю. Надо покопаться у них на сайте. А вот что считает AQUA, постараюсь объяснить. Коротко, если получится Есть такие задачи, которые в теории сложности алгоритмов называются NP-полными. Это когда при линейном росте размерности задачи время ее решения растет экспоненциально. Простой пример - полный перебор криптографических ключей (или паролей). Вы увеличиваете длину ключа на 1 бит, а пространство ключей увеличивается в 2 раза - значит надо в 2 раза больше времени на перебор. Если увеличить ключ на 10 бит - время возрастет в 2 в 10-ой степени, т.е. в 1024 раза. И так далее.

Есть еще такая NP-полная задача - квадратичная оптимизация. Там тоже при увеличении числа переменных время расчета растет экспоненциально. Для ее решения придумали адиабатический квантовый алгоритм. Но никто не смог доказать теоретически, что этот квантовый алгоритм дает экспоненциальное ускорение. Кстати, один квантовый алгоритм, дающий экспоненциальное ускорение, известен - это алгоритм Шора факторизации больших чисел (там все доказано). А вот для адиабатического алгоритма ученые мужи решили, что скорее всего этот вопрос можно решить только моделированием алгоритма на обычных компьютерах. Или построить многокубитный квантовый компьютер - и просто проверить Но это пока не получается. Вот AQUA и моделирует решение задачи квадратичной оптимизации на квантовом компьютере (условно говоря, на самом деле она решает эквивалентную квантовомеханическую задачу). И потом определяется, по какому закону будет расти время расчета на квантовом компьютере. Пока они опубликовали, кажется, результат до 96 кубитов - закон линейный. А это значит, что алгоритм обеспечивает экспоненциальное ускорение. Т.е. некоторые задачи, которые из-за гигантского времени расчета сложно решать даже с помощью армии кранчеров, можно будет решать на квантовом компьютере за разумное время. Вкратце, вот так

(с) Skyman

Ссылки по теме:

 

В какую категорию переместить этот проект?

http://distributed.ru/wiki/pro:aqua

http://www.boinc-af.org/content/view/1072/229/

http://wiki.bc-team.org/index.php?title=AQUA%40home/en

Це повідомлення відредагував nikelong: Sep 30 2010, 15:52

[YuRi]

Вот краткая выдерка из середины обзора (white paper) проекта, выложенного на сайте:

"Существуют алгоритмы, которые разрешены природой, но не могут быть выполнены на тех типах компьютерных систем, которыми мы располагаем сегодня. Это квантовые алгоритмы, требующие выполнения операций, которые разрешены квантовой механикой, но запрещены в классической физике. Для выполнения этих алгоритмов необходимо специальное аппаратное обеспечение (обычно называемое квантовыми компьютерами), разработанное с целью выполнять "квантовые операции", которые требуются для квантовых алгоритмов.
...
Важным классом квантовых алгоритмов является адиабатический квантовый алгоритм (здесь идет отсылка на презентацию 2002 года Scalable Architecture for Adiabatic Quantum Computing of NP-Hard Problems). Разработанные группой ученых Массачузетского Технологического Института (МТИ) в 2000 году, эти алгоритмы используют новаторский способ решения важных классов задач, с трудом поддающихся вычислительному решению (здесь - ссылка на отчет A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem). Эти алгоритмы вызвали огромное количество споров среди специалистов по физике и компьютерным наукам, поскольку не существует простого способа определить количество времени, необходимое для находжения решения задач, для которых эти алгоритмы были разработаны.
Некоторые теоретики вычислительной техники считают, что подобные алгоритмы не дают никаких преимуществ, тогда как многие другие, изучающие этот подход к решению задач, полагают, что (в сравнении с лучшими классическими алгоритмами) эти алгоритмы позволят получить экспоненциальный выигрыш по времени решения определенного класса задач (здесь - ссылка на научный проект МТИ Algorithms to Solve Average-Case NP-Hard Problems).
Определение времени, необходимого адиабатическому квантовому алгоритму для решения задачи, является важным научным вопросом, относящимся к наибольшей из остающихся открытыми проблем компьютерной науки. В дополнение к академической важности этого вопроса, он имеет также и черезвычайно высокую практическую важность для компании D-Wave Systems Inc., которая нацелена производство аппаратного обеспечения, исполняющего подобные алгоритмы."

Обзор, кстати, исчерпывающе краткий и довольно интересный. Рекомендую к прочтению.

Резюме:
Задачей проекта является симуляция квантового компьютера, выполняющего адиабатический квантовый алгоритм с целью экспериментального выяснения времени исполнения такого алгоритма для решения поставленной задачи.

Вывод:
Компьютерные науки, теория алгоритмов, вычислительная техника.

[Rilian]

статья в нью-йорк таймс

http://bits.blogs.nytimes.com/2008/12/22/d...antum-computer/

D-Wave Systems, a Canadian start-up, claims to have concocted a way of proving that its quantum computer is actually a quantum computer. But to pull off the proof, it needs thousands of people to volunteer spare time on their personal computers.

D-Wave chief technology officer Geordie Rose in front of the company’s latest quantum computer.

While founded in 1999, D-Wave remains a start-up because it has yet to ship a computer that customers can actually buy. Much of the company’s work is locked in the theoretical realm of quantum computing – long considered a sort of black arts backwater of the computing field full of promise but thin on near-term practicality.

In a bid to prove that it has a computer capable of quantum effects rather than just a regular computer, D-Wave has released some simulation software. The software centers on an algorithm designed to show off a quantum machine’s ability to solve complex problems more quickly than a traditional machine.

To crank through the simulation software, D-Wave is looking to spread the computing work across thousands of computers. It has embraced a type of distributed computing model similar to the SETI@home project where people download software that scans for signs of extraterrestrial intelligence as a background job on their PCs.

Once D-Wave collects the results of the simulations and processes the information, it will compare the simulation against an actual run of its latest quantum computer, which should be completed in the next few months. If the figures match up, then D-Wave will have shown that it really has a quantum machine, silencing skeptics, according to Geordie Rose, the company’s chief technology officer.

”Either the hardware will agree with the prediction or it won’t,” Mr. Rose said. ”If it doesn’t agree, then you don’t have a quantum computer. On the other hand, if the data tracks the predictions, you have smoking gun evidence that what you built is a quantum computer.”

Part of the quantum computing premise revolves around quantum bits, or qubits. These are similar to the 1 or 0 bits derived from transistors used in normal computers except that quantum mechanics, which works off the up and down spin of a nucleus, can hold more values simultaneously. So, where a pair of bits could represent just one choice out of 11, 00, 01 and 10, a pair of qubits could store all of these values. (The D-Wave simulation is for a machine with 128 qubits.)

The upshot of all this is that quantum computers should be capable of processing very complex problems with thousands of variables not practical for standard machines. And — voila — a whole new world of computing opens up.

D-Wave, which has received plenty of venture capital funding, is pitching the volunteer effort as being in the name of furthering science. It should be noted, however, that D-Wave hopes to be a for-profit company and could rent time on existing computers to churn through its simulations faster.

Perhaps the volunteers donating their PCs should ask for stock options to go along with each set of data they send back to the company.

ps: http://translate.google.com/translate_t?sl=en&tl=ru

[tribal]

про D-Wave довольно много противоречивых статей, и сама контора подогревает их выпуск, они до сих пор не предоставили ученым принципы работы своего компьютера - довольно много ученых склоняются к мнению что созданный компьютер является псевдо-квантовым, т.е. использует некоторые из элементов квантовой механики, вобщем открытие может оказаться мистификацией

[Rilian]

2008-12-23: Intel-based Mac users can now contribute to solving AQUA@home's quantum computing problems. A port of AQUA's application to Mac OS X is now available for use. The application was compiled and linked using GNU compilers under Mac OS X 10.5.6

[Death]

Rilian, ну и как? пощитал немножко?

[Rilian]

нет

еще не обновлялся до 10.5.6

[Skyman]

Когда выключаю BOINC, а потом снова включаю, время расчета юнита сбрасывается на ноль. И затем юнит начинает считаться сначала. Это только у меня так, или AQUA не умеет сохранять промежуточные результаты?

[YuRi]

У всех - клиент АКВЫ пока еще не сохраняет чекпоинты.

[Skyman]

Жаль, что не сохраняет. Хорошо, хоть юнит считается недолго

[(_Mystic_)]

Жаль, что не сохраняет. Хорошо, хоть юнит считается недолго

Время расчета вушек не предсказуемо, проверил на Q6600@3600:
228007 196749 27 Dec 2008 13:32:41 UTC 27 Dec 2008 14:26:55 UTC Over Success Done 1,050.64 8.31 14.96
227999 196741 27 Dec 2008 13:32:41 UTC 27 Dec 2008 15:59:19 UTC Over Success Done 1,780.41 14.08 25.34
227991 196733 27 Dec 2008 13:32:41 UTC 27 Dec 2008 18:57:23 UTC Over Success Done 11,465.51 90.67 163.21
227974 196716 27 Dec 2008 13:32:41 UTC 27 Dec 2008 17:58:39 UTC Over Success Done 7,579.43 59.94 107.90
227972 196714 27 Dec 2008 13:32:41 UTC 27 Dec 2008 14:04:18 UTC Over Success Done 32.68 0.26 0.47
Т.е. есть задания, которые очень долго считаются – более 3-х часов.
А проверял я для подключения на офисные слабенькие машины. В итоге постоянно считать этот проект пока у меня не получится.

[YuRi]

Та же самая фигня.
Более-менее стабильно можно считать на компах, где этот проект единственный. Да и то нет гарантии, что задача досчитается успешно - попадется на целероне длинное задание и будет считаться часиков 7. А потом юзер выключит машину. И завтра повторится то же самое...
Единственный плюс - практически не жрет память.

[Skyman]

Да, 3-4-часовые мне тоже попадались, хотя в основном меньше часа (на Атлоне 2500). На работе на старенькие целероны ставить нет смысла Хотя 3 часа - я б не сказал, что очень долго. Astropulse у меня считается более 8 суток

[YuRi]

На работе на старенькие целероны ставить нет смысла Хотя 3 часа - я б не сказал, что очень долго. Astropulse у меня считается более 8 суток

Не важно сколько считает; важно - сколько шансов закончить расчет. Чем длиннее задание, тем больше случайностей может произойти - отключится питание, юзер выключит машину, менеджер проектов переключится на другой проект... А при отсутствии чекпоинта это значит, что все расчеты прийдется начинать сначала, даже если до конца расчета оставались секунды.

[Rilian]

Кстати да, хорошо что напомнил, менеджер проектов по умолчанию переключает через 120 минут (2 часа). При ВЮ больше 2 часов это смертельно )