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

Для TSP с $N$ городами нужна машина, состоящая из $N-1$ слоев из $N-1$ щелей в каждом слое. Таким образом, каждую щель можно единственным образом задать парой целых чисел $(i, j)$. В дополнение к щелям машина содержит источник частиц («лазер»), расположенный в точке $S$, и детектор частиц в точке $D$ (см. рис. 1 ).
Рис. 1. Многощелевая интерференционная машина – TSP-решатель.
Существует $(N-1)^{(n-1)}$ возможных траекторий, по которым частица может попасть из точки $S$ в точку $D$. Траекторию можно единственным образом задать перечислением щелей на ней, например, траектория на рис. 2 задается так:
\[
S,(2,2),(3,4),(4,3),(5,5), D .
\]

Ясно, что указатели слоев можно опустить и описать эту траекторию последовательностью
$S, 2,4,3,5, D$.
Последовательность (1) можно принять в качестве кода маршрута коммивояжера по пяти городам, если только отождествить точки $S$ и $D$ с началом и концом маршрута (город 1). Тогда траектория (1) будет представлять маршрут $1,2,4,3,5,1$. Однако существуют траектории, которые не могут быть маршрутами коммивояжера, например, $S, 3,2,2,5, D$. Здесь город 2 посещается дважды, а город 4 пропущен.
Рис. 2. Траектория, соответствующая TSP-маршруту.
Следует избавиться от всех «запрещенных» траекторий и определить динамику движения частицы так, чтобы частица, проходящая сквозь машину, знала длину соответствующего TSP-маршрута.

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

Предположим, что внутренние состояния наших гипотетических частиц можно описать следующим кэт-вектором:
\[
\left|k ; c_{2}, c_{3}, \ldots, c_{N} ; p\right\rangle,
\]

где
\[
k \in(0,1, \ldots, N L), \quad c_{i} \in(0,1), \quad p \in(0,1) .
\]

Квантовое число $k$ будет измерять «число километров» маршрута, числа $c_{i}$ скажут, посещался $i$-й город или нет. Квантовое число $p$ не имеет отношения к TSP. Оно связано с дополнительной степенью свободы, необходимой для реализации принятой динамики.

Для описания работы машины все готово. Теперь рассмотрим часть траектории между двумя щелями из соседних слоев, $(i, m) \rightarrow(i+1, n)$.
Это – часть маршрута путешествующего торговца (TS) между городами $m$ и $n$. Предположим, что если частица проходит сквозь щель $(i, n)$, то квантовое число $c_{n}$ изменяется следующим образом:
\[
c_{n}=0 \rightarrow c_{n}=1 .
\]

Предположим также, что наша частица движется между щелями не в свободном пространстве, но в некотором поле, которое задано так, что квантовое число $k$ возрастает на отрезке траектории между щелями $(i, n)$ и $(i+1, m)$ как
\[
k \rightarrow k+d_{n m},
\]

где $d_{n m}$ – расстояние между городами $n$ и $m$. Соотвествующая динамика обсуждается в дополнении.
Предположим, что все частицы рождаются в точке $S$ в состоянии
\[
|0 ; 0,0, \ldots, 0 ; 0\rangle \text {. }
\]

После того как частицы пройдут сквозь машину, они окажутся в состоянии
\[
\sum_{\text {траектории }}\left|k ; c_{2}, c_{3}, \ldots, c_{N} ; p\right\rangle_{\text {траектория }}{ }^{*}
\]

Некоторые из траекторий в этой сумме соответствуют разрешенным TS-маршрутам. Легко понять, что это – те траектории, для которых все квантовые числа $c_{i}$ равны 1 , что гарантируется правилом (2). Для таких траекторий значение квантового числа $k$ равно длине соответствующего маршрута.

Представим теперь, что в точку $D$ помещен фильтр, который подавляет все состояния, кроме тех, для которых все $c_{i}$ равны 1 . Тогда состояния на выходе машины равны
\[
\left.\sum_{\text {траектории }} \mid \text { Длина маршрута } k ; 1,1, \ldots, 1 ; p\right\rangle_{\text {траектория }} \cdot
\]

Соответствующий фильтр должен состоять из серии устройств типа приборов Штерна-Герлаха, чувствительных к квантовым числам $c$ и поглощающих состояния с $c=0$. Заметим, что пока наши рассуждения следуют духу фейнмановских лекций [2].
Рис. 3. Устройство Штерна-Герлаха, измеряющее минимальное значение $k$.
Задача почти решена. Нужно только поместить в точку $D$ дополнительное устройство Штерна-Герлаха, на этот раз чувствительное к квантовому числу $k$. Оно должно разделить поток выходящих частиц на NL потоков, каждый из которых соответствует некоторому значению $k$ (см. рис. 3). Если снабдить выходные потоки детекторами частиц, то детектор у потока с $k=M L$ откликнется в том случае, если существует маршрут длины $M$. Из тех детекторов, которые откликнутся, можно выбрать детектор, соответствующий минимальному значению $k$. Он и укажет коммивояжеру кратчайший путь.