1
$\begingroup$

I have been under the impression that fault-tolerant universal quantum computation with nonvanishing thresholds requires at least two-dimensional connectivity of gates, not merely one-dimensional connectivity. However, this 1999 paper by Gottesman seems to challenge my belief.

Am I interpreting this correctly? If I lay out qubits on a line and I'm only allowed to perform faulty nearest-neighbor and next-nearest gates and local measurements of ancillas, can I perform universal quantum computation fault-tolerantly with a nonvanishing threshold?

I am still trying to understand the details of the construction.

In particular, I believe Gottesman argues that repeatedly concatenating a quantum error correcting code can nevertheless be done through local measurements of ancillas, many SWAP gates, and nearest-neighbor and next-nearest-neighbor gates along a line. To my understanding, the number of qubits are exponentially growing with the number of levels of concatenation, causing exponentially growing time delays when slowly shuffling qubits to measure stabilizer at a given level of concatenation. However, despite this, the recursive formulas for error rate at a given level of concatenation still give rise to a threshold.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The paper "Logical Qubit in a Linear Array of Semiconductor Quantum Dots" has a construction of a fault tolerant code with a threshold using nearest neighbor interactions on a 1d line of qubits.

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ +1 Thanks! I think I might have a gap in my knowledge of fault tolerance. It seems they only do error detection. Is that really enough to get a threshold theorem saying that $poly(n)$ gates on $n$ qubits can be simulated with arbitrarily low error up to multiplicative polylog overhead? (Maybe I should make that a separate question!) $\endgroup$
    – user196574
    Commented Aug 21 at 2:51
  • $\begingroup$ @user196574 they say error correction in the abstract $\endgroup$
    – Craig Gidney
    Commented Aug 22 at 16:01
  • $\begingroup$ You're right. I saw they did a bunch of distance-2 codes, but I jumped to conclusions, my bad! They also have distance-3 codes. $\endgroup$
    – user196574
    Commented Aug 22 at 17:00
  • $\begingroup$ Also, note to myself: I shouldn't have been so quick dismiss distance-2 codes; concatenating them allows for correction, not just detection; see journals.aps.org/pra/abstract/10.1103/PhysRevA.80.022313 for example of concatenating $[[4,1,2]]$ codes in 1d. $\endgroup$
    – user196574
    Commented Aug 27 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.