Кажется очевидным, что результаты теоретической физики значительно повлияли на ряд подполей теоретической информатики. Два примера этого
- Квантовые вычисления
- Результаты статистической механики, используемые в анализе сложности / эвристических алгоритмах.
Итак, мой вопрос: есть ли какие-то основные области, по которым я скучаю?
Моя мотивация очень проста: я физик-теоретик, который пришел в TCS с помощью квантовой информации, и мне любопытно, что касается других областей, где эти две области пересекаются.
Это относительно мягкий вопрос, но я не имею в виду, что это вопрос типа большого списка. Я ищу области, где перекрытие является значительным.
soft-question
quantum-computing
statistical-physics
physics
Джо Фитцсимонс
источник
источник
Ответы:
Методика поиска имитации отжига вдохновлена физическим процессом отжига в металлургии.
Отжиг - это термическая обработка, при которой прочность и твердость обрабатываемого вещества могут резко измениться. Часто это включает нагревание вещества до экстремальной температуры и последующее медленное охлаждение.
Имитация отжига позволяет избежать локальных минимумов / максимумов в пространствах поиска путем включения степени случайности (температуры) в процесс поиска. По мере того, как процесс поиска продолжается, температура постепенно охлаждается, что означает, что количество случайностей в поиске уменьшается. По-видимому, это довольно эффективный метод поиска.
источник
С другой стороны (от TCS к физике), состояния матричных продуктов, PEPS (спроецированные запутанные парные состояния), MERA (ансат многоуровневой реномализации переплетения) были в значительной степени основаны на идеях TCS, которые были адаптированы в квантовой теории информации. Все эти аббревиатуры представляют собой методы аппроксимации состояний квантовых спиновых систем, которые используются теоретиками конденсированного состояния, и во многих случаях эти методы, похоже, работают лучше, чем любые ранее известные инструменты.
источник
Сложные системы - это область, имеющая непосредственное отношение к анализу социальных сетей и к сетям в целом, и они были захвачены физиками в большом количестве, используя оружие из статистики и термодинамики. Был ли он захвачен физикой - это отдельная история.
источник
Результат Pour-El и Richards Adv. Математика 39 215 (1981) дает существование невычислимых решений трехмерного волнового уравнения для вычислимых начальных условий, используя волну для моделирования универсальной машины Тьюринга.
источник
Связь идет и наоборот. Некоторое время назад ученые-теоретики, работающие в области теории, заинтересовались относительностью. Они доказали результаты о том, как восстановить структуру пространства-времени из структуры причинности. Это что-то довольно знакомое теоретикам предметной области, где представляющие интерес beasic-объекты представляют собой частичные порядки, топология которых определяется порядком. Вы можете взглянуть на http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf
источник
Очень старый пример (который можно отнести к ответу Суреша, однако, это другой подход) - это влияние теории электрических сетей, например законов о схемах Кирхгофа, на комбинаторику, теорию графов и вероятность.
источник
Одной из областей, в которой было несколько приложений, но недостаточно ИМО, является аппроксимация дискретных структур или процессов с аналитическими аппроксимациями. Это большой бизнес в математике (например, аналитической теории чисел) и физике (все в статистической механике), но почему-то не пользуется популярностью в CS.
Известное применение этому было в дизайне Соединительной Машины. Это была массивно параллельная машина, и в рамках ее дизайна им необходимо выяснить, насколько велики размеры буферов в маршрутизаторе. Фейнман смоделировал маршрутизатор с помощью PDE и показал, что буферы могут быть меньше, чем традиционные индуктивные аргументы. Дэнни Хиллис рассказывает историю в этом эссе .
источник
Калибровочная теория для эвристических приближений к целочисленному программированию (несколько работ Миши Черткова ). Методы ренормгруппы для комбинаторного счета, гл. 10-12 Рудника / Гаспари «Элементы случайного блуждания». Применение интегрального разложения по Фейману (т. Е. Раздел 9.5.1) для подсчета самоходных прогулок. Что касается подключения к TCS, обратите внимание, что режим управляемости для приближенного подсчета на графиках зависит от скорости роста избегающих прогулок.
источник
Статистическая физика дала ученым-программистам новый взгляд на SAT, как показано здесь . Идея состоит в том, что по мере того, как отношение предложений к переменным, включенным в формулу 3-SAT, увеличивается примерно с 4 до 5, мы переходим от способности решать подавляющее большинство примеров 3-SAT к возможности решать очень мало. Этот переход рассматривается как «фазовый переход» в САТ.
Эта идея приобрела особую известность прошлым летом из предполагаемой статьи Деолаликара «P против NP».
источник
Ранняя теория распределенных систем, особенно статьи Лесли Лэмпорта и др., Оказала определенное влияние от Специальной теории относительности, чтобы получить правильную картину относительно (отказоустойчивого) соглашения о состоянии глобальной системы. См. Запись 27. ( Время, часы и порядок событий в распределенной системе , сообщения ACM 21, 7 (июль 1978 г.), 558-565) в сочинениях Лесли Лампорта , где Лампорт дает следующую справочную информацию о своем бумага:
источник
Я уточнил этот ответ расширенным ответом на MathOverflow на вики-вопрос сообщества Гила Калаи «[Что такое] книга, которую вы хотели бы написать » ».
Расширенный ответ стремится связать фундаментальные проблемы в TCS и QIT с практическими вопросами в области лечения и регенеративной медицины.
Этот ответ расширяет ответ Питера Шора , в котором рассматриваются роли состояний матричных произведений в TCS и физике. Два недавних опроса в Бюллетене AMS имеют отношение к матричным состояниям продуктов, и оба опроса написаны хорошо, не имеют ограничений по оплате и достаточно доступны для неспециалистов:
Геометрия Джозефа М. Ландсберга и сложность умножения матриц (2008)
Симплектическая теория вполне интегрируемых гамильтоновых систем Альваро Пелайо и Сан-Ву Нгока
Математическая арена для исследования Ландсберга - это секущиеся разновидности сортов Сегре , в то время как арена для исследования Пелайо и Нгока - это четырехмерные симплектические многообразия ... требуется некоторое время, чтобы понять, что обе эти арены являются состояниями матричных произведений, если рассматривать их соответственно с вычислительной точки зрения (Ландсбург) и геометрическая перспектива (Палайо и Нгок). Кроме того, Палайо и Нгок включают в свой обзор обсуждение Бабелона, Кантини и Дюшо полуклассического исследования модели Джейнса-Каммингса (отмечая, что модель Джейнса-Каммингса часто встречается в литературе по физике конденсированных сред и квантовым вычислениям ).
Каждая из этих ссылок идет далеко, чтобы осветить другие. В частности, в наших собственных (очень практичных) спин-динамических вычислениях было полезно понять, что квантовые пространства состояний, которые по-разному описываются в литературе как состояния тензорной сети, состояния матричного произведения и секущие многообразия многообразий Сегре, наделены богатыми возможностями. с особенностями, чья алгебраическая, симплектическая и риманова структура в настоящее время очень не полностью понята (как обзор Пелайо и Нгок).
В наших инженерных целях подход Ландсбурга / алгебраической геометрии , в котором пространство состояний квантовой динамики рассматривается как алгебраическое многообразие, а не векторное пространство, становится наиболее математически естественным. Это удивительно для нас, но, как и многие исследователи, мы находим, что набор алгебраических геометрических инструментов весьма полезен для проверки и ускорения практического квантового моделирования.
Квантовые симуляторы в настоящее время наслаждаются загадочным обстоятельством, что большие численные квантовые симуляции очень часто работают намного лучше, чем мы можем ожидать. Когда математики и физики придут к общему пониманию, эта озадаченность, несомненно, уменьшится, и удовольствие, несомненно, останется. Хорошо! :)
источник
Алгоритмы рисования графа на основе силы являются еще одним примером. Идея состоит в том, чтобы рассматривать каждое ребро как пружину, и расположение узлов графика соответствует нахождению равновесия в наборе пружин.
источник
Большая часть математики, которую мы используем, была изначально придумана для решения физических задач. Примеры включают исчисление (гравитация Ньютона) и ряд Фурье (уравнение теплопроводности).
источник
Недавно появилась статья, которая устанавливает связь между компьютерной безопасностью и вторым принципом термодинамики.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6266166
источник
Понятие потенциала связано со многими различными областями физики. В CS потенциал используется в амортизированном анализе структур данных. Мы можем посмотреть, как каждый шаг влияет на энтропию системы и, следовательно, получить среднюю (амортизированную) стоимость операции с заданной структурой данных. Это дало начало многим теоретически лучшим структурам данных, таким как куча Фибоначчи.
источник
чтобы добавить / заполнить некоторый пробел в текущих превосходных ответах / охвате - кажется, существует тесная связь между TCS и термодинамикой различными способами, которые еще не были полностью изучены, но являются границами активных исследований. есть точка перехода, связанная с SAT, но, возможно, есть точки перехода, связанные с другими (или даже всеми) классами сложности. точка перехода SAT связана с различием между «легкими» (P) и «жесткими» (NP) экземплярами, но, возможно, все границы класса сложности должны приводить к одному и тому же свойству, подобному точке перехода.
рассмотрим машину Тьюринга. он уже измеряет свою работу в обычно физических измерениях «времени» и «пространства». но обратите внимание, что он, очевидно, также выполняет одну единицу «работы» при переходе от квадрата к квадрату и совершает переход. в физике единицей работы является джоуль, который также является мерой энергии. Таким образом, кажется, что классы сложности имеют некоторое отношение к энергетическим уровням, границам или режимам.
Теория квантовой механики все чаще рассматривает пространство и время, вселенную, как своего рода вычислительную систему. Похоже, у него есть «минимальные вычислительные единицы», свойственные его природе, вероятно, связанные с длиной Планка. поэтому проверка минимальных машин Тьюринга на наличие проблем также подразумевает и относится к минимальным физическим / энергетическим системам или даже требуемым объемам пространства. [3]
Кроме того, ключевая концепция энтропии неоднократно проявляется в TCS и физике / термодинамике и может быть объединяющим принципом с еще более активными исследованиями, раскрывающими ее основную природу. [1,2]
[1] энтропия в теории информации , википедия
[2] Что такое CS энтропия , стековый поток
[3] Что такое объем информации? tcs.se
источник