Действительно ли квантовые отпечатки пальцев доказывают экспоненциальный размер волновых функций? Квантовое снятие отпечатков пальцев — это идея о том, что экспоненциально длинная классическая строка может быть закодирована в линейном количестве запутанных кубитов с использованием квантовых отпечатков пальцев. С экспоненциальной степенью точности, но не совсем, отпечатки двух разных экспоненциально длинных классических струн будут почти ортогональны.
Однако вся идея квантовых отпечатков пальцев основана на способности определить, идентичны ли два разных чистых квантовых состояния или ортогональны. Может ли существовать такой компаратор? Давайте сначала поработаем со сравнением кубитов. Наш гипотетический компаратор обладает тем свойством, что если два чистых кубита идентичны, он всегда выдает YES. Если они ортогональны, всегда выводится НЕТ. В других случаях он также может выводить. Тогда он определенно выведет НЕТ для и . По принципу суперпозиции он также должен был бы обязательно выводить НЕТ для линейной суперпозиции. . Он также должен был бы выводить YES для обоих и , а значит, и ДА для их линейной комбинации . Противоречие.
Если мы не можем сравнить, идентичны или почти ортогональны два квантовых отпечатка пальца, как тогда они должны работать? Является ли их кажущаяся экспоненциальность «фальшивкой»?
То, что снятие отпечатков пальцев говорит в пользу экспоненциального размера государства, сомнительно, но не совсем по той причине, которую вы изложили.
Во-первых, тест на ортогональность. Хотя вы правы в том, что не можете с уверенностью сказать, являются ли два состояния ортогональными, вы можете получить некоторую информацию, выполнив хорошо известный «тест обмена» на состояниях. Если у вас есть много копий состояний и вы выполняете тест для каждой пары, то вы можете довольно хорошо понять, ортогональны ли они. Иметь много копий возможно, потому что вы можете просто взять 100 отпечатков пальцев и назвать это большим отпечатком. Поскольку нас интересует только полиномиальный или экспоненциальный размер, не имеет значения, что вы возите около 100 из них одновременно.
Итак, учитывая, что вы на самом деле можете сказать, идентичны ли два отпечатка пальца или почти ортогональны, говорит ли это что-то о том, имеют ли состояния экспоненциальный размер? В данном случае не так уж и много, на мой взгляд, потому что вы можете сделать что-то очень похожее с классическими распределениями вероятностей. Имея документ, вы можете просто вычислить хеш-функцию и использовать ее как отпечаток пальца. Конечно, у хеш-функций есть коллизии, поэтому иногда два документа имеют одинаковый отпечаток пальца. Вы обходите это, выбирая хэш-функцию случайным образом. Затем ваш отпечаток состоит из хэша документа вместе с описанием того, какой хеш был выбран. Теперь, поскольку хэш был выбран случайным образом, один и тот же документ будет иметь разные отпечатки каждый раз, когда вы создаете отпечатки пальцев. Однако рассмотрим отпечаток пальца как распределение вероятностей, с одинаковыми весами среди каждой из хеш-функций, которые можно было бы выбрать. Если вы сравниваете квантовый и классический, то вы всегда должны допускать вариант, что классический объект может быть распределением вероятностей. Тогда одинаковые документы будут иметь одинаковые отпечатки пальцев (одинаковые распределения вероятностей), а разные документы будут иметь отпечатки пальцев, которые с очень высокой вероятностью различимы.
При этом есть по крайней мере один случай, когда квантовый отпечаток побеждает классический (даже с распределением вероятностей). Это тот случай, когда вам нужно сравнить два отпечатка пальца на предмет равенства, не имея доступа к исходному документу. Это обсуждается в разделе V Бурмана, Клеве, Массара, де Вольфа . Они также описывают случайные отпечатки пальцев и тест подкачки, о которых я упоминал выше.
Гораздо более убедительный аргумент в пользу состояния экспоненциального размера исходит из различных проблем коммуникации, где квантовая коммуникация экспоненциально лучше, чем классическая. Многие примеры можно найти в статье Бурмана, ссылка на которую приведена выше. Конечно, ничто из этого на самом деле не доказывает, что государство экспоненциально велико, и люди, вероятно, будут долго спорить об этом.