4430
правок
Отказоустойчивые квантовые вычисления: различия между версиями
Перейти к навигации
Перейти к поиску
Отказоустойчивые квантовые вычисления (посмотреть исходный код)
Версия от 19:10, 27 ноября 2020
, 27 ноября 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 31: | Строка 31: | ||
1. Серьезным результатом было открытие кодов квантовой коррекции ошибок (QECC). Примечательно, что несмотря на то, что квантовые ошибки могут быть непрерывными, кодов, которые исправляют дискретные ошибки, оказывается достаточно. (Измерение синдрома блока кода превращается в дискретное событие об ошибке). Первым квантовым кодом, обнаруженным Шором, был 9-кубитный код, состоящий из конкатенации трехкубитного кода <math>| 0 \rangle \mapsto | 000 \rangle, | 1 \rangle \mapsto | 111 \rangle</math> для защиты от ошибок инвертирования разряда, тогда как его дуальный код <math>| + \rangle \mapsto | + + + \rangle, | - \rangle \mapsto | - - - \rangle </math> обеспечивал защиту от ошибок инвертирования фазы. С тех пор было обнаружено много других QECC. Такие коды, как 9-кубитный код, способный исправлять ошибки разряда и фазы по отдельности, известны как коды Калдербанка-Шора-Стина (Calderbank-Shor-Steane, CSS) и имеют квантовые кодовые слова, которые одновременно являются суперпозициями кодовых слов классических кодов в базах <math> | 0 / 1 \rangle</math> и <math> | + / - \rangle</math>. | 1. Серьезным результатом было открытие кодов квантовой коррекции ошибок (QECC). Примечательно, что несмотря на то, что квантовые ошибки могут быть непрерывными, кодов, которые исправляют дискретные ошибки, оказывается достаточно. (Измерение синдрома блока кода превращается в дискретное событие об ошибке). Первым квантовым кодом, обнаруженным Шором, был 9-кубитный код, состоящий из конкатенации трехкубитного кода <math>| 0 \rangle \mapsto | 000 \rangle, | 1 \rangle \mapsto | 111 \rangle</math> для защиты от ошибок инвертирования разряда, тогда как его дуальный код <math>| + \rangle \mapsto | + + + \rangle, | - \rangle \mapsto | - - - \rangle </math> обеспечивал защиту от ошибок инвертирования фазы. С тех пор было обнаружено много других QECC. Такие коды, как 9-кубитный код, способный исправлять ошибки разряда и фазы по отдельности, известны как коды Калдербанка-Шора-Стина (Calderbank-Shor-Steane, CSS) и имеют квантовые кодовые слова, которые одновременно являются суперпозициями кодовых слов классических кодов в базах <math> | 0 / 1 \rangle</math> и <math> | + / - \rangle</math>. | ||
2. Коды QECC позволяют использовать квантовую память или общаться по шумному каналу. Для вычисления, однако, должна быть возможность расчета на основе кодирования последовательности состояний в отсутствие первичного декодирования. Операция считается ''отказоустойчивой'', если она не может привести к коррелированным ошибкам внутри блока кода. При наличии n-битного мажоритарного кода все классические вентили могут быть применены ''перпендикулярно'': закодированный вентиль можно реализовать посредством применения незакодированного вентиля к битам i каждого блока кода, <math>1 \le i \le n</math>. Эта операция является отказоустойчивой, так как один отказ влияет не более чем на один бит в каждом блоке и, таким образом, отказы не могут распространяться слишком быстро. Для квантовых кодов CSS вентиль с контролируемым отрицанием CNOT: | 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. Однако эта грубая прикидка не является жесткой, поскольку эффективный коэффициент ошибок плохо определен, и логические ошибки не обязательно должны соответствовать той же модели, что и физические ошибки (например, они не будут независимыми). | Однако Шор не доказал существование ''константного'' допустимого уровня шума, или порога шума. Несколько групп исследователей – Ахаронов/Бен-Ор, Китаев, Книлл/Лафламм/Зурек – пришли к идее использовать меньшие по размеру коды и многократно выполнять конкатенацию процедуры поверх себя самой. Интуитивно представляется, что при наличии кода с расстоянием 3 (т. е. кода, который исправляет любую одну ошибку) можно ожидать, что «эффективный» коэффициент логических ошибок закодированного вентиля не будет превышать cp2 для некоторой константы c, потому что одну ошибку можно исправить, а две – нет. Тогда эффективный коэффициент ошибок для дважды кодированного вентиля должен составлять не более c(cp2)2; а поскольку эффективный коэффициент ошибок убывает дважды экспоненциально относительно числа уровней конкатенации, то накладные расходы при достижении коэффициента ошибок 1/N составляют только poly(logN). Порог для улучшения – cp2 < p, p < 1/c. Однако эта грубая прикидка не является жесткой, поскольку эффективный коэффициент ошибок плохо определен, и логические ошибки не обязательно должны соответствовать той же модели, что и физические ошибки (например, они не будут независимыми). | ||