Shtetl Оптимизированное

Во-первых, если вы не внесли свой вклад в усилия по оказанию помощи в Гаити, вы можете Сделай так (связанная с этим благотворительная организация была рекомендована американским гаитянином, работающим в MIT CSAIL). Хотелось бы мне сказать что-то более полезное об этой трагедии, но я этого не делаю.

Последние пару дней я был на QIP'2010 в Цюрихе, Швейцария. У меня были предчувствия, даже до приезда, что это будет необычайно крутой QIP. Находясь на ПК, я знал всю мощь технической программы и узнал, что явка - 320 участников - будет рекордно высокой. Мои позитивные чувства только усилились, когда я увидел следующее в коридоре моего отеля:

Когда я вошел в лекционный зал, мое жужжание достигло лихорадочного предела, и на каждом месте я обнаружил гигантские, изысканные швейцарские шоколадные батончики.

Но я точно знал , что этот QIP зародится, когда мой бывший советник Умеш Вазирани выступил со вступительным пленарным докладом на тему «Новые мосты между информатикой и квантовыми вычислениями». Умеш выделил несколько событий, в том числе:

  1. отношения В прошлом году я заметил, что между проблемой BQP и проблемой полиномиальной иерархии и Обобщенной гипотезой Линиала-Нисана.
  2. = PSPACE QIP прорыв Джейн и соавт. (на основе недавнего метода обновления мультипликативных весов из классической информатики).
  3. недавние прорывы в криптографии на основе решетки (наиболее известный, Джентри полностью гомоморфная система шифрования ), которая черпала вдохновение в работах по квантовым вычислениям Одеда Регева пять лет назад.
  4. Работа Бродбент, Фицсимонс и Кашефи и независимо Ааронов, Бен-Ор и Эбан (за что я заплатил кусочки Приз Ааронсона 25,00 $ ), который позволяет «классическому» верификатору (оснащенному возможностью посылать одиночные, незапутанные кубиты через канал) проверять произвольные квантовые вычисления; и что Умеш проиллюстрировал историей о проверщике, расследующем заявления тенистой компании, летящей ночью, под названием «Q-Wave».

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

Сочетание шоколадной плитки (которую я уже ел) и Умеша, проповедующего так много правды с кафедры, было небесным.

Удивительно, но последующим переговорам удалось сохранить импульс. Даниэль Готтесман рассказал о своем Работа с Сэнди Ирани о квантовой сложности трансляционно-инвариантных плиточных и гамильтоновых задач. Предоставляя инструменты, позволяющие сказать что-то полезное о сложности вычислений, даже в тех случаях, когда единственным бесплатным параметром является размер системы, Gottesman и Irani открывают некоторые захватывающие возможности для дальнейшей работы. Джордан Керенидис рассказал о усилие доказать аналог Валиант-Вазирани доказательство теоремы изоляции для QMA (Квантовый Мерлин-Артур). Стефано Пиронио рассказал о том, как можно эксплуатировать нарушения неравенства Белла генерировать длинную случайную строку, начиная с короткого случайного начального числа, предполагая только локальность законов физики, и не предполагая ничего о надежности ваших генерирующих случайность устройств. Это наблюдение, которое, по моему мнению, представляет большой концептуальный (и, возможно, даже практический) интерес, связано с так называемым «Теорема свободной воли» Конвея и Кочена, а также результат, который я доказал восемь лет назад в моем обзор книги Стивена Вольфрама. Для Конвея и Кохена, тем не менее, мотивация заключалась в том, чтобы доказать, что «субатомные частицы имеют свободную волю» (странная интерпретация, которую я никоим образом не одобряю!), В то время как для меня мотивация состояла в том, чтобы доказать, что Вольфрам был неправ. Ни я, ни (насколько я знаю) Конвей и Кочен не думали о том, как использовать ретроспективное явление для генерации случайных чисел. (Кстати, если кому-то интересно, мои слайды со вчерашнего утра Вот .)

Также на QIP этого года было много волнений по поводу эффективного моделирования квантовых систем, происходящих в природе, с использованием новейших методов для уменьшения порядка моделей (включая MERA, состояния матричных произведений, квантовую выборку метрополий, законы области…). Надеюсь, я не просто заставил Джона Сидлеса упасть в обморок от волнения.

Полный график Вот ; не стесняйтесь спрашивать в комментариях о любых разговорах, которые я не упомянул. Если есть достаточно интереса, я мог бы также написать последующее сообщение об остальной части конференции.