Отказоустойчивые квантовые вычисления: различия между версиями

2. Коды QECC позволяют использовать квантовую память или общаться по шумному каналу. Для вычисления, однако, должна быть возможность расчета на основе кодирования последовательности состояний в отсутствие первичного декодирования. Операция считается ''отказоустойчивой'', если она не может привести к коррелированным ошибкам внутри блока кода. При наличии n-битного мажоритарного кода все классические вентили могут быть применены ''перпендикулярно'': закодированный вентиль можно реализовать посредством применения незакодированного вентиля к битам i каждого блока кода, <math>1 \le i \le n</math>. Эта операция является отказоустойчивой, так как один отказ влияет не более чем на один бит в каждом блоке и, таким образом, отказы не могут распространяться слишком быстро. Для квантовых кодов CSS вентиль с контролируемым отрицанием CNOT: <math> | a, b \rangle \mapsto | a, a \oplus b \rangle</math> может применяться перпендикулярно аналогичным образом. Однако сам по себе вентиль CNOT не является универсальным, поэтому Шор также предложил отказоустойчивую реализацию вентиля Тоффоли <math> | a, b, c \rangle \mapsto | a, b, c \oplus (a \wedge b) \rangle</math>. Как для коррекции ошибок при использовании неисправных вентилей, так и для начального этапа подготовки требуются дополнительные процедуры. Кодирование <math> | 0 \rangle</math> представляет сильно запутанное состояние и трудно для подготовки (в отличие от <math>0^n</math> для классического мажоритарного кода).

Однако Шор не доказал существование ''константного'' допустимого уровня шума, или порога шума. Несколько групп исследователей – Ахаронов/Бен-Ор, Китаев, Книлл/Лафламм/Зурек – пришли к идее использовать меньшие по размеру коды и многократно выполнять конкатенацию процедуры поверх себя самой. Интуитивно представляется, что при наличии кода с расстоянием 3 (т. е. кода, который исправляет любую одну ошибку) можно ожидать, что «эффективный» коэффициент логических ошибок закодированного вентиля не будет превышать cp2 для некоторой константы c, потому что одну ошибку можно исправить, а две – нет. Тогда эффективный коэффициент ошибок для дважды кодированного вентиля должен составлять не более c(cp2)2; а поскольку эффективный коэффициент ошибок убывает дважды экспоненциально относительно числа уровней конкатенации, то накладные расходы при достижении коэффициента ошибок 1/N составляют только poly(logN). Порог для улучшения – cp2 < p, p < 1/c. Однако эта грубая прикидка не является жесткой, поскольку эффективный коэффициент ошибок плохо определен, и логические ошибки не обязательно должны соответствовать той же модели, что и физические ошибки (например, они не будут независимыми).