Autor: Frank6626

• Simon’s Algorithm – The Problem
• Circuit
• Analyse the Circuit and the Result
• Appendix A: Complexity of Algorithms
• Appendix B: Complexity Classes
• Appendix C: Hadamard Calculations
• Appendix D: Auxiliary Calculation regarding the component-wise XOR
• Appendix E: The probability of success in Simon’s problem
• Sources

Simon’s Algorithm – The Problem

How can quantum computing bring a real advantage compared to classical approaches? Sometimes the answer could be more difficult as expected: ‚Dequantization‘ describes, under which conditions classical algorithms achieve a performance comparable to quantum algorithms, see e.g. [1] 

Nevertheless: Simon’s algorithm is an early example (1994) of how a quantum algorithm has an exponential improvement over the classial approach. The problem reads as

takes a binary string of length n to another such binary string (doesn’t make too much sense, but anyway 😊). When is f(x) = f(y)? In general, this is not known. Therefore, restrict the functions by imposing an additional requirement:

 What does it mean? E.g. for the first component: 

OR

if and only if there is a nonzero string r in {0,1}ⁿ for which

So, what is r?  Classically by brute force:

possible values to consider, so at best (refinement, optimizations) it is

i.e. exponentially hard (see Appendix B). Simon’s algorithm: O(n), i.e. linear in n (see Appendix A)!

Since r has n bits, we need at least n qubits to represent the answer of what is r

Circuit

Essentially H-gates and some Oracle function, 2n qubits. As we will see: the register 2’s role is to be entangled with the first register in order to encode information about r (via U_f) into the phase of register 1 and in the end to be measured in order to force the collapse into some quantum state and releasing this information about r with the first register

• Initial state: |0>^⨂n ⨂ |0>^⨂n  Applying H gives a balanced superposition of the first n qubits (the last n qubits are still in the initial state):   

• The input to U_f is |x>⨂ |y>, the output

Apply U_f :

• Apply H to the first n qubits results in

(see Appendix C)

Probability for observing a particular |u>: 

It will be shown, f(x) entangles the U_f-input |x> (uniform superposition of the first n qubits after the first H) with the second register, and by this information about r is created in the phase of the quantum state which can be measured!

Analyse the circuit and the result

First consider r = 0:

hence x and y are both 0 or 1. Hence the sum over all x equals the sum over all f(x), just in another order! With x = y:

Seeing any of the

values of |u> when measured is

If the circuit is measured many times and sees this distribution of the |u>, r might be 0

Now consider r not equal 0:

Then f is two-to-one:

with x₁ and y₁ are either 0 and 1 or 1 and 0.

Hence: x ≠ y, but f(x) = f(y) for some r: for

exactly two values from {0,1}ⁿ are mapped via f to

Too see this: the inverse of XOR is XOR itself:

But this looks like f(x) = f(x+r), which implies a periodic function with period r, i.e. f is repeating itself  after r values (e.g. cos(x) = cos(x+r) with r = 2π)

Probability of observing a particular |u> (note that Appendix D is used in the third line):

The uniform distribution of kets on all |u> is such that u ∙ r = 0. Suppose we execute the circuit quite often and measure n-1 binary strings u₁, …, u_n-1 . Assume(!) u_k are linearly independent vectors:

u₁ ∙ r = u₂ ∙ r =  … u_n-1 ∙ r = 0

Because of the linear independency it follows, that those n-1 equations are uniquely solvable for (r₁, …, r_n) = r (Gaussian elimination, 0 is the n^th column)

What time does it take to find those n independent u_k among the 2ⁿ binary n-strings?

Finding n linearly independent strings in a collection of n+k nonzero binary n-strings produced by the circuit is

(see Appendix E)

Hence by e.g. choosing k = 30, the chance of failure is less than 1:10⁹! In other words, running the circuit n+30 times gives nearly the probability of 1 to correctly determine r. Hence: O(n)!

QED

(quod erat demonstrandum, not Quantum Electrodynamics 😊)

Appendix A: Complexity of Algorithms

a) If an algorithm is of

with t some number > 1, then the algorithm is of ‘polynomial time’

b) An algorithm of O( f(n) ) can be improved quadratically, if it can be replaced by one of 

c) Exponential improvement: O(log f(n) )

d) Example: an algorithm takes

days to complete (~2740 years). Quadratic improvement: 103 days (~2,74 years), exponential improvement: 6 days!

Appendix B: Complexity Classes

Complexity class P are all problems solvable in

with a deterministic algorithm (vs. a nondeterministic algorithm involving probabilities)

The class NP are all problems whose solution can be checked in

If P = NP is not known!

Example: it is not known if there is a deterministic way of factoring a composite integer (a positive integer greater than 1 that has more than two factors; the smallest one is 4) in

But if known, the check is just multiplying those numbers. Hence deterministic factoring is in NP, but maybe not in P

There are (many) more classes, just two of them: assume P ≠ NP:

NP-Hard: problems at least as hard to solve as the most difficult ones in NP

NP-Complete: a NP-Hard problem can be reduced with an

algorithm to a NP problem

O( f(n) ): number of operations ≤ c f(n).  The problem is at most as hard as c f(n) 

O'( f(n) ): number of operations ≥ c f(n).  The problem is at least as hard as c f(n)

Appendix C: Hadamard Calculation

Recall:

Consider |u>, u = 0 or 1:

Hence it can be written as: 

Note: the powers of -1 changes the signs of the kets, called phase change.

For bit strings of length 2, i.e. from

the basis kets are |00>, |01>, |10>, |11> := |u> = |u1u2>. With that:

Start the circuit:

Now apply U_f:  

Finally, H again on the first n qubits:

Appendix D: Auxiliary Calculation regarding the component-wise XOR

If u is the zero-bit string:

All other cases: assume first a single u_k = 1, the rest of the string are 0’s

x in {0,1}ⁿ corresponds to every possible binary string, and each bit x_i goes independently over {0,1}, Hence:

For all i ≠ k: u_i = 0, hence

For i = k:  u_k = 1, hence

hence the product is 0. This can be generalized:

gives 0 for any non-zero u!

Appendix E: The probability of success in Simon’s problem [2]

Each appliance of U_f gives a random vector y satisfying r·u = 0 mod 2. The solution space, i.e. all vectors orthogonal to r, forms a subspace of dimension n−1. To recover r uniquely, one needs n−1 linearly independent equations

A set of n+x random vectors from a (n-1) dimensional subspace of an n-dimensional vector space (with components restricted to 0 and 1) will at some point contain with high probability a linearly independent subset!

Now arrange a matrix with n+x rows (coming from n+x measurements) and n-1 columns (being the desired number of linearly independent vectors)

Now one can formulate two equivalent questions:

• Among the n+x row vectors (each (n−1)-dimensional), do some n−1 of them form a linearly independent set?

• Are all n−1 column vectors (each (n+x)-dimensional) linearly independent?

Due to the rank theorem they have the same answer!

(rank theorem:  

i) the row rank is the maximum number of linearly independent rows

ii) the column rank is the maximum number of linearly independent columns

iii) it holds: for any matrix M: „row rank“=“column rank“ (for proof see e.g. [3])

)

So intuitively, the rows are measured, but the columns are ‘easier’ to analyze:

Pick any column vector. The probability of being non-zero is 

(that a specific bit of the chosen string is 0 has probability 1/2  independently of all other bits). Take this string as a first basis vector.

Now recall that here everything is mod2, that means for the subspace spanned by this first basis vector:

{c · v, c in {0,1}, v being the first column basis vector}, i.e. the subspace contains only two vectors: c = 0 is the zero vector and c = 1 is the vector itself! This holds for all n+x dimensions, hence there are

vectors in total

Therefore, the probability of a randomly selected second column vector to be linearly independent of the first is

Continuing this argument for all n-1 columns give

What is a ‘helpful’ lower bound for q (q representing now the probability that there are n-1 linearly independent vectors)? For non-negative numbers a, b, c, … whose sum is less than 1 it holds (1-a) (1-b) (1-c) … exceeds 1 – (a + b +c …), hence

and furthermore (Weierstrass product inequality)

(The last step intuitively:

is greater than 2 times summing the largest minus term …)

So, finally e.g. for x = 20:  q > 0,9999995 that the n-1 vectors are linearly independent.

Intuitively, why only such a small number of additional measurements? Again, this is essentially because of the mod 2: with growing x the (dimension fixed-) subspace containing

vectors gets much smaller than the total subspace of

vectors and with growing x it becomes more and more unlikely that a randomly selected column vector lands in the subspace

Sources

• [1] ‚A quantum-inspired classical algorithm for recommendation systems‘ by Tang, 2019  (arxiv.org/pdf/1807.04271)
• [2] Quantum Computer Science An Introduction by N. David Mermin, Cambridge University Press, 2007,  Appendix G
• [3] ‚Rank–nullity theorem‘, Wikipedia (https://en.wikipedia.org/wiki/Rank-nullity_theorem)
• ‚Dancing with Qubits‘, R.S. Sutor, <packt>, second edition, 2024

1. Introduction
   • Double Split Experiment
   • RSA, Shors Algorithm and Secrets
2. Mathematical & Quantum Physics Preliminaries
   • a) Some Properties of Complex Numbers
   • b) Linear Transformations and (Unitary) Matrices
   • c) Some Geometry
   • d) Some Group Theory
   • e) Eigenvalues and Eigenvectors
   • f) Tensorproducts
   • g) Root of Unity & Summation Formula
3. One Qubit
   • a) Bloch Sphere
   • b) Bra and Kets
   • c) Quantum State of a Qubit
   • d) Observables and Expectations
   • e) Quantum Gates
4. Two Qubits
   • a) Entanglement
   • c) Multi-Qubit Gates: The Quantum H^{⨂ n} Gate
   • d) The Quantum CNOT/CX Gate
5. Circuits
   • a) Simple Circuits
   • b) Amplitude Maximization & Interference
   • c) Inversion About The Mean
6. Sources

1. Introduction

Note: most of the pictures are generated with Claude.ai

Double Split Experiment – The Importance of Measurement

Wave-particle-duality of light: if not measured through which split the photon is travelling, it behaves like waves, i.e. the interference pattern looks like

But if looked up, it behaves like a particle!

In general: on a very small scale, the world behaves not very intuitive …. (Quantum Mechanics, Quantum Electrodynamics (Photons), Quantum Chromodynamics (Quarks), Supersymmetric String Theory, Quantum Groups, …)

RSA, Shors Algorithm and Secrets

‘Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer’ by Peter Shor, 1994, [1]

The described quantum algorithm can ‘efficiently’ factor large integers – something classical computer struggle with

Many of todays encryption systems, including RSA (Rivest–Shamir–Adleman), rely on the difficulty of integer factorization.

‘Harvest now, decrypt later’ (HNDL), see e.g. a whitepaper from Mastercard(!) from 2025: ‘Migration to post quantum cryptography – white paper’, [2]

On a more general note: when do quantum algorithms start to outperform classical ones? See e.g. [3]

2. Mathematical & Quantum Physics Preliminaries

This is by no means a thoroughly introduction into the topics, more a mentioning what will be needed

a) Some Properties of Complex Numbers

b) Linear Transformations and (Unitary) Matrices, [4]

• Let U_n and V_m be vector spaces over R of dimension n, m respectively. Let u₁ and u₂ be in U and s₁ and s₂ in R. The function L: U -> V is a linear map if L(u₁ + u₂) = L(u₁) + L(u₂)  and L(s₁u₁) = s₁L(u₁). When U = V, L is called a linear transformation of U

• Assume L(u₁) = Au₁, where A is a n x m matrix:  L(u₁+u₂) = A(u₁+u₂) = Au₁ + Au₂  and L(s₁u₁) = A(s₁u₁) = s₁Au₁, hence the matrix A is a linear transformation

•What are the characteristics of linear transformations that preserve the length, i.e. ||Lv|| = ||v||? They are unitary:

A complex square matrix U is unitary if

with the adjoint matrix

Remark: The matrices corresponding to gates/operations on qubits are all unitary! Examples: Pauli matrices

c) Some Geometry

Polar coordinates:     P = r cos(θ) + r sin (θ)

Eulers formula in C:  z = r cos (θ) + r sin(θ) = r e^θi , 0 ≤ θ < 2π

Also: z = r e^2πφi , 0 ≤ φ < 1

Binary form: (used later as approximation of φ)

Base 10:  1/4 + 1/8 = 0.375₁₀

In base 2: 0 x 2^-1 + 1 x 2^-2 + 1 x 2^-3 = .011₂

Another example: 0.2 has no exact finite binary expansion, but repeating decimals: 

Note: a base 10 rational number has either a finite binary expansion or repeats in blocks, with the repeating block being a base 10 rational number In general: φ ≈ b₁2^-1 + … + b_m2^-m =: (0.b₁b₂..b_m)₂ , hence

d) Some* Group Theory

A collection of objects or transformations with an operation * is called a group if it holds

• Closure

• Associativity

• Unique identity element

• For every object in G exists a unique inverse

If in addition a*b = b*a, G is a commutative or abelian group

Examples: (R,+) is an abelian group, (N,+) is not. Often symmetry operations form a group (e.g. the Bloch sphere representation of quantum states, see later)

*Some more: the (finite) monster ( https://plus.maths.org/content/enormous-theorem-classification-finite-simple-groups ) in the moonshine 😊 ( https://www.quantamagazine.org/mathematicians-chase-moonshine-string-theory-connections-20150312/ )

e) Eigenvalues and Eigenvectors [5]

nxn matrix A: if Av = λv, v is an eigenvector of A and λ the corresponding eigenvalue;  (A – λ I) v = 0 and since v ≠ 0: (A – λ I) not invertible and hence det (A – λ I) = 0

hence 1 and -1 are eigenvalues. This generalizes to any diagonal matrix!

has no eigenvalues in R, 1+i and 1-i.  For any (nxn)-matrix A over C, det (A – λ I) can be completely factored on C, so A has n eigenvalues and n corresponding eigenvectors

A is diagonizable if a matrix V exists, so that D = V^-1AV; this corresponds to a change of basis vectors: D represents the same linear transformation as A but in a different basis

Now a complex matrix is diagonizable if all its eigenvalues are different (in case of repeated eigenvalues it may still be possible, but not in general)

Spectral theorem: A nxn complex matrix A is Hermitian if

Then all eigenvalues of A are real and the corresponding eigenvectors build an orthogonal basis of Cⁿ

Be U a complex unitary matrix:  U = V⁺DV with V and D unitary. Since V⁺=V^-1: VU⁺V = D. In other words: there is a unitary change of basis so that U is diagonal

Note: Solving the eigenvalue problem in quantum mechanics means finding the state (eigenfunction/-vector) the particle can occupy and the physical quantities (eigenvalues) it can possess in that state

f) Tensorproduct

V, W are two finite dimensional vector spaces: V ⨂ W is generated by addition and scalar multiplication of all formal objects v ⨂ w for each v in V and w in W

 If {v1,…vn} and {w1,…,wn} are bases for V and W, then {v₁ ⨂ w₁, …, v_n ⨂ w_m} are basis vectors of V ⨂ W

X, Y are two additional vector spaces, if f: V -> X and g: W -> Y are linear mappings, then so is

      f ⨂ g: V ⨂W -> X ⨂ Y with (f ⨂ g)(v ⨂ w) = f(v) ⨂ g(w)

For 2×2 matrices:

For vectors: v = (v₁,v_2,v₃), w = (w₁, w₂):  v ⨂ w = (v₁w₁,v₁w₂, …,v₃w₂)

For R² ⨂ R² or C² ⨂ C²: e₁ ⨂ e₁ = (1,0) ⨂ (1,0) = (1,0,0,0), … , e₂ ⨂ e₂ = (0,0,0,1). Note: C² ⨂ C² ⨂ C² has dimension 2³

g) Root of Unity & Summation Formula

n in N, then the n^th root of unity is ω in C with ωⁿ=1. There are n n^th roots of unity and 1 is always one of them.

ω is a primitive n^th root of unity, if every other root of unity can be written as ω^k for some k in N

Example: all roots of unity for n = 3?

n = 1:  One first root of unity, 1

n = 2:  Two second roots of unity, 1 and -1

n = 3:  With Euler’s formula e^φi = cos(φ) + sin(φ)i, |e^φi| = 1 (note that φ = 2π/3 is a 1/3 rotation around the unit circle), third roots of unity:

Because 3 is prime, ω is primitive:

In general: 

Now:

xⁿ – 1 = (x-1) (x^n-1 + x^n-2 + … + x + 1)

For every n^th root of unity:  xⁿ – 1 = 0 ,  hence from the above 

x = ω = 1 and for ω ≠ 1: 

With  

(adding the same set of roots in a different order!)

With the Kronecker delta function  δ_j,k = 0 if j ≠ k and 1 if j = k:

Extended summation formula:

3. One Qubit

a) Bloch Sphere

A classical bit is 0 or 1 and only in one of those states at any given time!

Qubit representation on the Bloch sphere:

When measured, a qubit is always in states |0> or |1>, but during computing it can be in any (quantum) state on the sphere!

Formally: the qubit is in superposition of |0> and |1> in C² ,

  |ψ> = a |0> + b |1>

with |a|² + |b|² = 1 (unit sphere), where a, b are probability amplitudes

Because qubits are not ‘independent’ to each other as classical bits (superposition of quantum states), huge parallelism is possible.

A single computation acting on 300 qubits can achieve the same effect as 2³⁰⁰ simultaneous computations acting on classical bits!

b) Quantum Mechanics Notification: Bra and Kets

What are |0> and |1>? 

For a vector v, write bra

and for w, ket

Then for example:   

|0> and |1> build the standard orthonormal basis for C²:  |0> = (1,0) = e₁, |1> = (0,1) = e₂ . Other orthonormal basises are 

and

A qubit state has length 1, and any linear transformation must preserve this length! Hence all matrix representations of such transformations are unitary (and hence invertible).

See later for ‘quantum circuits’: all ‘gates’ (operations = linear transformations) are reversible! Only the measurement operation is not! In other words: a quantum circuit is applying unitary matrices to vectors, representing qubit states

c) Quantum State of a Qubit

Quantum state:   |ψ> = a |0> + b |1>  with  ||ψ|| = < ψ | ψ >² = 1

|ψ> = a |0> + b |1> =  r₁ e^φ’i |0> + r₂ e^φ’’i |1>  =  e^φ’i (r₁ |0> + r₂ e^{(φ’-φ’’)i} |1>

Multiplying |ψ> by a phase e^φ’i  doesn’t change it in the sense that the probability of obtaining |0> or |1> is not changed, i.e. there is no observable difference! Hence there are two degrees of freedom for a qubit:

1)Magnitudes r₁, r₂ with r₁²+r₂² = 1

2)Relative phase φ = φ₁ – φ₂

|ψ> of a single qubit is therefore  |ψ> =  r₁ |0> + r₂ e^φi |1> with  r₁, r₂ in R,  r₁²+r₂² = 1,  0 ≤ φ < 2π

d) Observables and Expectations

Measurement of a quantum system:

1. The measurement of a specific observable can be represented by a unitary operator U (matrix)
2. The quantum system is described by a Hilbert-Vector |ψ>
3. A measurement is the application of U to |ψ>
4. Results of the measurement are Eigenvalues u_i of U
5. Probability for a specific u_i: | <u_i| ψ> |²

Let M₀ = |0><0| , M₁ = |1><1| , |ψ> = a |0> + b |1>

  < ψ| M₀ | ψ> = |a|²    probability for |0>

  < ψ| M₁ | ψ> = |b|²    probability for |1>

M₀ and M₁ are observables! The ‘expectation’ <A> of an observable A given the state | ψ> is < ψ| A| ψ>

e) Quantum Gates

Remember: The matrices corresponding to gates/operations on qubits are all unitary!

Examples:

Quantum X Gate                      

corresponds to the Pauli matrix

σ_x |0> = |1> ,  σ_x 1> = |0>, i.e. the ‘not’ gate

Bloch sphere: a quantum state is rotated around the x-axis by π. Rotation around the y-axis  σ_y ,  around the z-axis σ_z

Hadamard Gate

H changes the basis from  |0>,  |1>  to   |+>,  |->

The Quantum R^z_φ Gates: generalize σ_x to 

and define

Then: S|0> = |0>,  S|1> =  e^{(π /2)i} |1> = i |1>,  |1> is an eigenvector of S with eigenvalue i

4. Two Qubits

a) Entanglement

2 qubits q₁, q₂ are in superposition states represented in C² ⨂ C² by a linear combination of |00>, |01>, |10>, |11> (corresponds to 4 possible outcomes of measurement, since each qubit will drop to |0> or |1>)

and e.g.

Through measurement the qubits are irreversible projected to |00>, |01>, |10> or |11> with probability |a₀₀|² , |a₀₁|² , |a₁₀|² , |a₁₁|²  respectively. Entanglement is one of the main differences to classical computing! Why? Let’s do an example of Entanglement:

Let q₁, q₂ be in the state

i.e. when measured (very often) it will be half of the time in |01> and half of the time in |10>, but never in |00> or |11>

Now measure q₂ only and let’s say the result is |1>. This can come only from |01> or |11>, but |11> is impossible, hence q₁ must be |0>! This is ENTANGLEMENT

A 2-bit quantum state |ψ> in C² ⨂ C² is entangled if and only if it cannot be written as a tensor of two 1-qubit kets: If

then |ψ> is not entangled

For the example above: assume it is entangled, then there are a₁, b₁, a₂, b₂ in C, with

Hence:

-> assumption not correct!

This can be generalized to n-qubit systems with states having 2ⁿ dimensions and the state space can be written as (C²)^{⨂ n}

b) Multi-Qubit Gates: The Quantum H^{⨂ n} Gate

For 2 qubits, quantum gate operations are 4×4 unitary square matrices (for 10 qubits: 2¹⁰x2¹⁰ matrices). 2 Examples:

First the quantum H^{⨂ n} gate

with

This matrix puts both initialized qubits into a balanced (equal amplitudes) superposition!

Notation: the set of n-qubits for (C²)^⨂n composed of only 0s and 1s are called computational bases. E.g. for C² ⨂ C² ⨂ C² |000>, |001>, |010>, |011>, |100>, |101>, |110>, |111>. These are the same as |0>₃     |1>₃     |2>₃     |3>₃     |4>₃     |5>₃     |6>₃     |7>₃

For 3-qubits: 

with

beeing a normalization constant

Classical: three bits have 2³ states, but only one at a time. The 3-qubit state H^⨂3|0>₃ contains all 8 possible basis kets at the same time!

c) The quantum CNOT or CX gate

Now the second gate:

This gate creates entangled qubits (!), ‘C’ stands for ‘CONTROLLED’ (black dot, control qubit; the other: target)

Two input states |ψ₁>, |ψ₂> and hence two outputs (reversable):

• if |ψ₁> = |1> -> output: |ψ₁>,  X|ψ₂>

• if |ψ₁> = |0> -> output: |ψ₁>,  |ψ₂>

Example:

Eigenvalues and Eigenstates of CNOT:

Eigenstates of the Pauli X (bit-flip) operator in the |0>, |1> basis (also called Z basis):

To find the eigenvalues: det(X−λI)=0  

Eigenvectors, ∣ψ> = a|0> + b|1>

i) λ = +1: (X−I) ∣ψ> = 0, hence a = b; normalizing:

ii) λ = -1: (X+I) ∣ψ> = 0, hence a = -b; normalizing:

Behavior X operator:

• X|+⟩ = +|+⟩ (unchanged)

• X|−⟩ = −|−⟩ (phase flip)

• X|0⟩ = |1⟩ (bit flip)

• X|1⟩ = |0⟩ (bit flip)

Note: ∣+> = H∣0> and  ∣−> = H∣1>, and in addition

i.e. H rotates the eigenstates of X onto the eigenstates of Z; |+>, |-> is also referred as X basis

5. Circuits

a) Simple Circuits

Quantum register: a collection of qubits used for computation, all qubits in a register are initialized to |0>

Quantum circuit: a sequence of gates applied to one or more qubits in a quantum register

Simple circuits:

Note: there is no CLONE gate that can duplicate the quantum state of a qubit! (No backups for qubits!)

b) Amplitude Maximization & Interference

3-qubit quantum register state:

Balanced superposition (all coefficients are equal):   

Let’s assume one of the basis kets is the solution to some problem. Possibility of an amplitude amplification for that ket?  For a quantum algorithm in general: have the results of the final qubit measurements to correspond with high probability to the best solution

How? First: flip the sign of the ket in question (e.g. |010> by U_|010> being I₈ except that the (3,3) entry is -1)

c) Inversion about the mean

Next: inversion about the mean

S = {s_j} finite in R, m the mean of those numbers. Create T = {t_j = 2m – s_j}. Then it holds:

•The mean is still m

•The mapping is reversible

•S_j=m ,  then t_j = s_j = m

•T_j – m = m –s_j

•S_j < m:   t_j > m ,  and s_j > m:   t_j < m

Example: S = {-1,5; 1,5; 1,5; 1,5} -> m = 0,75, T = {3; 0; 0; 0}

Now back to  |φ> = H^{⨂ 3} |000>; define

Then U_φ performs an inversion about the mean!

Negating the amplitude and applying U_φ multiple times leads to an increase of the desired probability

But: one can’t apply those two steps too many times, because at some point the desired amplitude is decreasing and the others are increasing again!

Note:

• How many times to maximize the probability? Approximation:  

• Generalization of U_φ:  Groover diffusion operator   H^{⨂ n}( 2 |0>^⨂n <0|^⨂n  –   I^{⨂ n} )H^⨂n

In this context often used:

Oracle function for some question := black box resulting in 1 for yes and 0 for no; oracles cannot answer random questions, they respond to specific queries.

For classical data: f:{0,1}ⁿ -> {0,1}; for quantum computing for basis kets it could be e.g. f(|x>_i) = |1> for one special |x>_i, |0> otherwise. f can be represented by a unitary operator U_f (see the blog about Simon’s Algorithm for an detailed example of how an oracle is working)

6. Sources

[1] ‚Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer‘ by Shor, 1995 (https://www.arxiv.org/abs/quant-ph/9508027)

[2] ‚Migration-to-post-quantum-cryptography-WhitePaper‚ by Mastercard, 2025

[3] ‚Multi-objective optimization offers bold new path to quantum advantage‘ by Woerner et al. (IBM Quantum Blog), 2026(https://www.ibm.com/quantum/blog/multi-objective-optimization)

[4] Lineare Algebra, Gerd Fischer, vieweg studium, 9. Aufl. 1989

[5] Vorlesungen über Physik, Band III: Quantenmechanik, Feynman/Leighton/Sands, Oldenbourg, 2.Aufl. 1992

‚Dancing with Qubits‘, R.S. Sutor, <packt>, second edition, 2024

1. Surface Code – Introduction [1], [2], [3], [4]
2. Logical Operators
3. Holes [4], [6]
4. Moving Holes
5. Braiding [6]
6. Braiding 2 Logical Qubits
7. Equivalence to (Multiple-Qubit) CNOT Gate
8. Sources

1. Surface Code – Introduction [1], [2], [3], [4]

One can get rid of the periodic boundary conditions of the toric code to get a flat 2-dim surface (or planar) code, encoding a single qubit (which is easier to realize then the toric code)

To start: split the boundary of the lattice (solid lines) into a ‘smooth’ (at the top and the bottom) and a ‘rough’ (left and right) boundary, the latter carrying no qubits

A second lattice represented by the dotted lines is called dual lattice (it holds: all properties for X-stabilizers on the lattice  can be translated to Z-stabilizers on the dual lattice!)

A path along the edges is an element of a group called the group of one chains, [5]. Allow only edges carrying a qubit gives a subgroup: the group of one chains relative to the rough boundary (because the edges of the rough boundary are omitted)

As for the toric code, ancilla qubits (black dots) are introduced in addition to the physical qubits (white dots)

Each data qubit is coupled to two ‘measure’ Z qubits and two ‘measure’ X qubits. Each measurement qubit is coupled to 4 data qubits

What’s happening? The system is in some initial state, and then all the stabilizers are measured. This will force the state into a simultaneous eigenstate of all the stabilizer operators, but the eigenvalues may not all equal 1. Hence apply the error corrections to move the state into the code space

Now start some quantum algorithm and after a first step measure again all the stabilizers to detect errors in order to correct them. Now execute the quantum algorithm’s second step … and repeat!

A measure Z qubit, when performing the measurement cycle (i.e. measuring a stabilizer ZZZZ), forces its neighboring data qubits a, b, c, d into an eigenstate of

Similar, the stabilizer

is measured by a X qubit and forcing its neighboring data qubits a, b, c, d into an eigenstate of

The first ZZZZ and XXXX measurement takes whatever initial data qubit state there is into an entangled |ψ> that is a simultaneous eigenstate of all measurements across the lattice (called quiescent state). If no error occurs, every measurement cycle will give |ψ>, because all the X- and Z-stabilizers commute with each other

For every relative one-chain c define Xc and Zc, obtained by letting X respectively Z act on the qubits along the chain. Similar for co-chains along the dual lattice

The red line relative one-chain is ‘open-ended’ (since the rough boundary is removed, also called ‘zero boundary’), and is the equivalent to a closed loop on a torus! Similar, the blue line represents a relative co-chain with zero boundary on the dual lattice

As for the toric code: introduce Xv for each vertex and Zf for each tile, building an abelian subgroup S, creating a 2-dimensional code space (i.e. the space of all states left invariant by all tile operators and all vertex operators), hence encoding one logical qubit. This code is the surface code

The logical operators are the ones created by the blue and red line: Zc and Xc*

2. Logical Operators

See again the lattice below: there are 18 data qubits and 17 measurement qubits (not shown), hence there are 2*18 degrees of freedom (each qubit lives in an 2-dim Hilbert space, hence 218 distinct states) and 2*17 constraints from the stabilizer measurements, because each stabilizer is reducing the number of degrees of freedom by a factor 2 (since the outcome of each measurement is +1 or -1)

Hence there are two unconstrained degrees of freedom, and therefore the surface code lattice describes one (error-corrected) logical qubit! The lattice state is therefore 

where |u>L is the state of the ‘free’ logical qubit, |v> the fully stabilized state of the remaining (data) qubits. What are the logical operators 

Consider

From the toric code it shouldn’t come as a surprise, that XL commutes trivially with all X-stabilizer, but also with the Z-stabilizers (because it flips none or two qubits of the Z stabilizer). Analogously: ZL

And since

these two operators manipulate |u>L without affecting |v> and are not in the stabilizers, hence are logical operators! Note:

Hence there is only one non-trivially distinct XL operator for the whole lattice, regardless of the lattice size!

3. Holes [4], [6]

How to realize more than 1 logical qubit on a lattice of physical qubits?

By releasing the constraints coming from the stabilizers: ‘turn off’ one or more of the internal measure-X and measure-Z qubits, i.e. they are not included in the measurement cycle anymore (although the qubits are still there)! This alters the code space, but the ‘logical’ meaning of the quantum state is untouched

See e.g. [7] chapter 10.5: a stabilizer group S on n physical qubits generated by g independent generators stabilizes a

dimensional subspace. Hence: the code space gets two extra dimensions by removing a single stabilizer Zf: 

Define

connected to the boundary and

both sharing one data qubit (called ‘Z-cut’ qubit), hence anticommute (and are therefore not in the stabilizer group). The Z-cut qubit (adding two degrees of freedom) plus the logical operators … build a logical qubit! Note that you couldn’t define a non-trivial XL operator for the Z-cut qubit if connected to the Z boundary

Analogously: X-cut qubit

One can get rid of the boundary condition: removing pairs of measure-X and -Z qubits!  Defining the (local!) operators appropriately and ignoring 2 of the 4 added degrees of freedom, a single logical qubit is created and can be manipulated, see [4]

To summarize: In the surface code, a „hole“ (defect) defines a logical qubit with two logical operators: a string connecting the hole to a boundary (or another hole) of the same type and a string encircling the hole

4. Moving Holes

It holds, that multiple-qubit gates can be realized by moving entangled logical qubits around on a 2D lattice while preserving the surface code error protection. Passing one hole of a two-hole qubit between the two holes of a second qubit, “braiding” the logical qubits together, one performs a logical CNOT on the two qubits!

Move a hole. a) The lower Z-cut builds the logical qubit with

First exclude the Z-stabilizer from the next measurement cycle, i.e. the data qubit 6 will not be measured by a Z-stabilizer, but measured separately by the new, extended operator

(to preserve the error correction, b). c) Redefine

After the first measurement cycle the original Z-cut qubit (lower hole in a) is ‘turned on’ and the second surface code cycle is done. Define

and the original Z-cut qubit is moved with the logical operators

Note: the operator extension could lead to a change in sign for the resulting state, hence so-called Byproduct operators are introduced:

where z and x describe if a sign switch really happened (and only then those operators are applied)

This hole movement can be generalized to multi-cell movements (still in just one step of the code cycle)

5. Braiding [6]

A braid transformation can entangle two logical qubits, in a way that makes the braid transformation equivalent to a logical CNOT!

Start with a single Z-cut qubit and the XL operator with 3 data qubits (by the way: this is the Heisenberg description of quantum mechanics, describing the evolvement of the system by the evolvement of the operators, in contrast to the Schrödinger picture, where the operators are constant and the wave functions (quantum states) are evolving over time; both descriptions are equivalent considering measurement outcomes, see e.g. [8]). The grey square is the idle second hole. Then start moving with the first cycle, measuring the isolated data qubits with the measurement eigenvalues

Note that the braid cannot be done in a single multi-cell move, because this would isolate the area enclosed by the braid. Third picture: extended

Then the second measurement cycle is done, again measuring the isolated data qubits separately. Next: extending

including now next to a closed loop of operators also the original chain of X operators. The closed loop is completely stabilized by the nine X stabilizers

and hence one can reduce the X operator chain to

which is identical to

(and hence the new state is living in the original code space and can be compared to the original state!). The signs can be handled by corresponding Byproduct operators

Now for the ZL operator:

Start the movement, the first measurement cycle gives ±1 for every

Extend

Now

are turned on and the new

is formed:

Note: now wait, because there can occur errors in the isolated data qubits during the move, the error measurement and correction needs to be applied by executing d-times the surface code measurement cycle (d the distance of the code)). Then the second move, finally producing a closed loop with

which is identical to ZL up to the sign, again handled by Byproduct operators

6. Braiding 2 Logical Qubits 

a) The braid path could enclose another logical qubit, here braiding a Z-cut qubit by a X-cut qubit (being equivalent to a logical CNOT-gate):

As shown in the picture, in the end there is an operator XL1’’ being identical to XL1 (potentially up to a sign) and since the X-cut hole inside the loop is not stabilized, the loop operator resolves not to a simple product of measurement outcomes, but an operator XL2 on the second qubit:

The Z-cut hole moves clockwise around the X-cut hole, moved by the Z-string

The dotted lines in the second picture are the shared edges between adjacent plaquettes and will vanish, e.g. between

The outer boundary loop then crosses the ZL2 string of the X-cut hole, hence multiply the boundary loop with ZL2 and again the shared edge vanishes.

In a surface code, a logical operator can be freely deformed by multiplying with stabilizers, i.e. push the string around without changing the logical operator. The ZL2 string has been deformed to run around the inner boundary of the X-cut hole (picture 3, black dotted line)

Example calculation: let ZL2​ be the logical Z operator for the X-cut hole. Name the physical qubits surrounding a X-cut hole as follows, where ZL2 runs from top to bottom through the center (the holes, like in picture 2 above):

Hence multiplying all (operators on different qubits commute):

but this is exactly the loop!

Back to c) and the corresponding picture: restore ZL2 leaving a logical operator on the first qubit

The first qubit hole is braided by a loop of Z operators through the second qubit, but as the loop preserves its closed form with both moves (at the ‚end‘ of the first move is now the identity operator), it does not generate a chain or loop of operators that act on the second qubit

7. Equivalence to (Multiple-Qubit) CNOT Gate

CNOT on 2 qubits, transforming 16 outer products of I, X, Z, Y, only 4 are independent (because of, e.g., (Z⊗X) = (Z⊗I) ∙ (I⊗X)):

This is exactly the transformation described before by the braiding of a Z-cut qubit as the control and a X-cut qubit as the target!

Note: Unfortunately, the surface code does not allow a representation of a universal set of quantum gates by braids – doing this requires the use of a more sophisticated physical equivalent called non-abelian anyons, see e.g. [9]

8. Sources

• [1] ‚Quantum error correction: the surface code‘ by christianb93, 2019  (leftasexercise.com/2019/04/08/quantum-error-correction-the-surface-code/)
• [2] ‚Quantum codes and quantum error correction‘ by christianb93, 2018  (github.com/christianb93/QuantumComputing/blob/master/QEC/QuantumErrorCorrection.pdf)
• [3] ‚Quantum codes on a lattice with boundary‘ by Bravyi et al., 2024  (arxiv.org/pdf/quant-ph/9811052)
• [4] ‚An introduction to the surface code‘ by Cleland, 2019  (researchgate.net/publication/360361427_An_introduction_to_the_surface_code)
• [5] ‚Chain Complexes‘ by Wright, 2024  (people.eecs.berkeley.edu/~jswright/quantumcodingtheory24/scribe%20notes/lecture14.pdf)
• [6] ‚Surface codes: Towards practical large-scale quantum computation‘ by Fowler et al., 2012  (arxiv.org/pdf/1208.0928)
• [7] ‚Quantum Computation and Quantum Information‘, Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2010
• [8] ‚From Heisenberg and Schrödinger to the P vs. NP Problem‘ by Weinstein, 2025  (arxiv.org/html/2511.07502v1) 
• [9] ‚Non-Abelian Anyons and Topological Quantum Computation‘ by Nayak et al., 2008  (arxiv.org/pdf/0707.1889)
• [10] ‚Poking holes and cutting corners to achieve Clifford gates with the surface code‘ by Brown et al., 2017 (arxiv.org/pdf/1609.04673)

1. Stabilizer Generators [1], [2], [3]
2. Logical Operators
3. Example: Laflamme’s code [4], [5]
4. Toric Code
   • Errors [7]
   • Error Correction
   • Ground / Excited Atom States [6]
   • Parity Measurement
   • Logical Operators
5. Appendix A: Spectral Theorem
6. Appendix B: CNOT Eigenvalues and Eigenvectors
7. Sources

1. Stabilizer Generators [1], [2], [3]

The Pauli group Pn on n qubits are all tensor products of the single-qubit Pauli operators {I, X, Y, Z}. A stabilizer group S is a subgroup of Pn satisfying

1. Contains the identity operator
2. All elements of S commute with each other
3. Any product of two elements in S is in S
4. It does not contain the negative identity operator

Generators: a minimal set of operators in S that can produce all the other elements, e.g. consider

where the index indicates the qubit, it operates on and fulfilling 1. to 4. One can obtain all elements by

alone, hence these are stabilizer generators with

In other words: the stabilizer generators define the syndrome measurements!

There is a one-to-one correspondence between stabilizer groups and the quantum error-correcting codes:

The codespace is defined uniquely by the set of all states such that Si|ψ> = |ψ>  for all Si in S

The codewords (states) can be derived with an orthogonal basis of the codespace

Example: recall the three-qubit repetition code (9 Qubit Shor Code), where |000>, |111> is an orthonormal basis for the codewords defined by

2. Logical Operators

Now: how to operate on the stable, encoded logical qubits, without leaving the codespace?

In order to preserve the code space, these operators have to commute with all stabilizers, because otherwise they could e.g. change the syndrome and hence corrupting the original, encoded data

In general, for logical operators:

1. They commute with all elements in S and leave the codespace invariant
2. They are not in the stabilizer group
3. Logical operators for the same logical qubit anticommute, i.e. act non-trivially on the codewords

An (easy) example is again the three-qubit repetition code: the logical operators are  

So, every Pauli Operator on encoded qubits is either

• a logical operator
• or a stabilizer
• or an error (not commuting with at least one stabilizer and taking the state out of the codespace)

3. Example: Laflamme’s code [4], [5]

The following 5 qubit code is the smallest error correcting code capable of correcting arbitrary Pauli errors (i.e. unwanted applications of X, Y or Z gates on a single qubit)

These operators commute and are linearly independent, hence the code subspace has dimension

The logical basis states |0>L and |1>L of the 5-qubit error correcting code span the 2-dimensional codespace (embedded within the 32-dimensional Hilbert space of 5 physical qubits, i.e. the +1 eigenspace of the 4 stabilizer generators). The logical operators are 

Note: an example of an error code is

commuting with all Si, but acting non-trivial on the codespace

And analogously:

Now encode a data qubit in an arbitrary state |ψ> = a|0> + b|1> to

Syndrome measurement circuit for a single qubit error:

Since there are 4 independent stabilizers, there are 16 possible syndromes, which can be corrected:

4. Toric Code

Consider a 2-dimensional discrete lattice LxL with periodic boundary conditions (hence the lattice can be thought as a surface of a doughnut, i.e. a torus) and on each edge of this lattice a qubit is placed, [6]

face operator Zf = applying Pauli Z operators to all qubits of a tile (I for all other qubits, red). Stabilizer generators are all the Z⨂ Z⨂ Z⨂ Z for all tiles

vertex operator Xv = product of Pauli X operators acting on the qubits on the edges of a vortex (I for all other qubits, blue). Stabilizer generators are all the X⨂ X⨂ X⨂ X for all vertices

Since the product of all Zf stabilizer generators yield I, and the same holds for the product of all Xv stabilizer generators, the toric code (derived from the abelian group of all Zf and Xv) with 2L*L physical qubits can encode 2 logical qubits (independent of L!):  

the term in brackets being the number of stabilizer generators per operator type minus the constraint

Errors [7]

To be a valid stabilizer code:

• all Z operators commute with themselves, analogously all X; Z and X acting on different qubits commute, but also on the same qubit, since the overlap is always two qubits due to the periodic boundary conditions
• Stabilizer generators need to be a minimal set. Due to the two constraints of the product of all Xv and Zf respectively: remove any single X and single Z stabilizer (expressible through all the other Z or X operators), to build a minimal set

Consider a chain of X errors. The two Z stabilizer generators will measure the parity -1 at the ends of the chain because of the odd number of X errors in both faces. The actual error chain is not detected, since an even number of X errors in a face will give +1

Hence a closed loop of X errors is not detected, but there is a corresponding X operator in the stabilizer generators and hence this is not a physical error (the encoded logical state is not changed!)

There are (undetectable) closed X error loops which are not in the stabilizers! They represent  non-trivial logical errors and are non-contractable loops on the torus surface, the shortest  being of length L! Hence for 2L*L qubits, encoding 2 logical qubits, the toric code is called    

Analogously: Z errors

Error Correction

X errors and Z errors can be detected and corrected independently. E.g. the error depicted here:

Only the two grey tiles are known to be errorous and are corrected by the X operators along the yellow line. Correcting means here: after applying the ‘yellow’ line, the still existing errors plus the corrected ones keep the encoded logical state unchanged!

Note: choosing the shortest path between two -1 syndrome measurements will not  always correct the error at hand and there are different strategies to try to correct the situation (e.g. Edmonds (classical!) Blossom Algorithm, see e.g. [8])

Real physical errors are local, e.g. an atom interacting with its environment. But the logical errors span the entire lattice. Hence for a logical error to occur, L correlated errors forming a non-contractable loop have to arise independently! If the probability for an X error is p, the probability for a closed loop would be

which vanishes with lattice size!

Note: there is a finite fault-tolerance threshold pth for the toric code (and the surface code)

• If p < pth, then increasing L exponentially suppresses the logical error rate, p being the single qubit error rate
• If p > pth, the errors will overwhelm the correction code

For the surface code, pth is roughly 1% (one of the highest thresholds known for QEC codes and achievable with today’s hardware, see e.g. [9]: Google’s 3rd generation Sycamore processor)

The intuitive reason for the threshold existence is that random independent errors below some error density are unlikely to form large connected clusters but rather stay local (and are hence correctable).

Above the threshold, errors percolate (for directed percolation see e.g. [10]) and can form system-spanning chains, behaving like logical errors

The issue is, that the code is expensive:

Ground / Excited Atom States [6]

Consider 

which is Hermitian and hence can be thought as an operator of a physical system. The eigenstates of the Hamiltonian correspond to energy levels

From the Spectral Theorem, e.g. [11] and appendix A: it exists a basis {|ψi>}  of eigenstates diagonalizing H and each basis vector is an eigenstate of all face and vertex operators

Let x_vi and z_fi be the corresponding eigenvalues, then |ψ_i> is an eigenvector of H with eigenvalue 

This expression becomes minimal if all z_fi and x_vi are +1, hence |ψ_i> belongs to the code space (!) and corresponds to a ground state of H!

Note: Errors (adding z_fi or x_vi that are -1, hence increasing the eigenvalue of H) correspond to excited states!

Parity Measurement

A Z error on a data qubit propagates backward through CNOT onto the ancilla as an X-eigenvalue flip, which is what the X-stabilizer measurement circuit exploits when reading out the syndrome

Start with, what happens to the control’s X-eigenvalue when the target carries an X-eigenvalue? CNOT for the X basis:

So after CNOT, the control qubit carries the target (X-) eigenvalue. Let’s do the second expression explicitly:

In general: the control’s X-eigenvalue after CNOT equals the product of the control’s with the target’s X-eigenvalue:

I.e: CNOT ‘copies’ X backward (target -> control) in the X basis

This is the Z-copy rule but mirrored: CNOT ‘copies’ Z forward (control -> target) in the Z basis:

The ancilla starts in |0> (Z-eigenstate, eigenvalue +1) and the CNOTs have the data qubits as controls and the ancilla as target; the data qubits each are in some Z-eigenstate |zi> in {|0>, |1>}

CNOT rule: | c,t > -> | c, c XOR t>, i.e. the target flips if the control is in |1> (Note: this is only true in the Z basis, if the control is in superposition, the result is an entangled Bell state and not a copy, consistent with the no-cloning theorem!)

Hence the ancilla (here the target!) accumulates the XOR of the control bits:

The ancilla qubit is in an eigenstate of Z, measuring gives either +1 (no Z error detected) or -1 (Z error detected)

If a Z error occurs, it flips the sign, but doesn’t change the Z-eigenvalue (state) when measured: Z|0> = +|0>,  Z|1> = -|1>, i.e. the XOR parity is unchanged. Therefore a Z error is not detected by a Z-stabilizer! But by the X-stabilizer: X-error on a data qubit gives either X|0> = |1> or X|1> = |0>, hence changing the XOR parity accumulated on the ancilla!

Practical advantage of the toric code: stabilizer measurements only involve 4 neighboring qubits, no long-range interactions are required. For Z stabilizers, detecting X-errors, the parity measurement circuit looks like

Measuring the parity for

the ancilla qubit is |0> for parity +1 (no error detected) and |1> for -1 (error detected)

For the X stabilizer detecting Z errors the circuit looks like below, since an X-error on a data qubit flips the ancilla qubit via a CNOT gate (as seen before in detail)

Logical Operators

For completeness, what are the logical operators of the toric code? A logical operator is defined as an operator that:

1. Commutes with all stabilizers → has trivial syndrome → is undetectable
2. Does not belong to the stabilizer group → actually does something non-trivial to the logical state

This is exactly the definition of a worst-case error — one that the code cannot detect or correct

But: the logical operators are exactly the non-contractual loops mentioned earlier!

Zc1 be the operator acting with Z-operators on all qubits along the line c1, commuting with all tile operators.

Two qubits of the X operators of vertex V belong to c1. Zc1 commutes with Xv, because it picks up two -1 signs! But it doesn’t belong to the stabilizers

Analogously Zc2

Hence the two ‘line’ Z-operators act as logical operators on the two logical qubits |0>L and |1>L causing a phase shift for |1>L

Along the same argument regarding the blue dotted lines: Xc’1 and Xc’2 are logical operators acting on |0>L or |1>L by flipping the encoded state

5. Appendix A: Spectral Theorem

nxn matrix A: if Av = λv, v is an eigenvector of A and λ the corresponding eigenvalue;  (A – λ I) v = 0 and since v ≠ 0: (A – λ I) not invertible and hence det (A – λ I) = 0

Notes:

Now a complex matrix is diagonizable if all its eigenvalues are different (in case of repeated eigenvalues it may still be possible, but not in general)

Spectral theorem: A nxn complex matrix A is Hermitian if 

Then all eigenvalues of A are real and the corresponding eigenvectors build an orthogonal basis of

Be U a complex unitary matrix: 

In other words: there is a unitary change of basis so that U is diagonal

Note: Solving the eigenvalue problem in quantum mechanics means finding the state (eigenfunction/-vector) the particle can occupy and the physical quantities (eigenvalues) it can possess in that state

6. Appendix B: CNOT Eigenvalues and Eigenvectors

Eigenstates of the Pauli X (bit-flip) operator in the |0>, |1> basis (also called Z basis) is

To find the eigenvalues: det(X−λI)=0:

Eigenvectors, ∣ψ> = a|0> + b|1>:

a) λ = +1: (X−I) ∣ψ> = 0, hence a = b; with normalizing: 

b) λ = -1: (X+I) ∣ψ> = 0, hence a = -b; normalizing:

Behavior X operator:

• X|+⟩ = +|+⟩ (unchanged)
• X|−⟩ = −|−⟩ (phase flip)
• X|0⟩ = |1⟩ (bit flip)
• X|1⟩ = |0⟩ (bit flip)

Note: ∣+> = H∣0> and  ∣−> = H∣1>, and in addition

i.e. H rotates the eigenstates of X onto the eigenstates of Z; |+>, |-> is also referred as X basis

7. Sources

• [1] Quantum Computation and Quantum Information, Nielsen, Chuang, Cambridge Press
• [2] ‚Stabilizer codes for quantum error correction‘ by Chelluri et al., 2025  (pennylane.ai/qml/demos/tutorial_stabilizer_codes)
• [3] ‚Quantum codesand quantum error correction‘ by christianb93, 2018  (github.com/christianb93/QuantumComputing/blob/master/QEC/QuantumErrorCorrection.pdf)
• [4] ‚Perfect Quantum Error Correction Code‘ by Laflamme et al., 1996  (arxiv.org/abs/quant-ph/9602019)
• [5] ‚Stabilizer Codes and Quantum Error Correction‘ by Gottesman, 1997 (arxiv.org/pdf/quant-ph/9705052)
• [6] ‚Quantum error correction: an introduction to toric codes‘ by christianb93, 2019  (leftasexercise.com/2019/03/25/qec-an-introduction-to-toric-codes/)
• [7] ‚Toric code‘ by IBM Learning, (quantum.cloud.ibm.com/learning/en/courses/foundations-of-quantum-error-correction/quantum-code-constructions/toric-code)
• [8] ‚PyMatching: A Python Package for Decoding Quantum Codes with Minimum-Weight Perfect Matching‘ by Higgott, 2022  (dl.acm.org/doi/full/10.1145/3505637)
• [9] ‚Suppressing quantum errors by scaling a surface code logical qubit‘ by Google Quantum AI, 2023  (research.google/blog/suppressing-quantum-errors-by-scaling-a-surface-code-logical-qubit/)
• [10] ‚Renormalized field theory of collapsing randomly branched polymers‘ by Janssen et al., 2009  (arxiv.org/pdf/0907.3430)
• [11] Vorlesungen über Physik – Band 3: Quantenmechanik, Feynman, Leigthon, Sands, Oldenbourg Verlag

1. Single Bit-Flip or Phase-Flip Error [1]
2. Correcting an arbitrary single qubit error
3. Sources

1. Single Bit-Flip or Phase-Flip Error [1]

After showing, that QEC is necessary, next is … how? One of the first approaches was published by Peter Shore in 1995: his approach stabilizes a single logical qubit against any error by encoding 9 physical qubits. Start with the three-qubit bit flip (error correction) code, using entanglement:

(1) Start with any |ψ> = a|0> + b|1> and extend it by 2 initialized qubits:

(2) Create an entangled state via 2 CNOT gates:

(3) Assume a single qubit flip: |ψ1> = a|000> + b|111> (no flip) or a|001> + b|110> or a|010> + b|101> or a|100> + b|001>

Define operators for the 2 measurements: 

1. P0 = |000><000| + |111><111|  no error
2. P1 = |100><100| + |001><001|  q1 flipped
3. P2 = |010><010| + |101><101|  q2 flipped
4. P3 = |001><001| + |110><110|  q3 flipped

<ψ1|Pi|ψ1> in {0, 1}, representing only the information which error occurred; hence the original qubit state is not destroyed by the measurement!

For example.: <ψ1|P2|ψ1> for |ψ1> = a|010> + b|101> is 1, and 0 for all others, hence from the measurement it can be derived that the second qubit was flipped

(4) How to represent the operators Pi? With 2 ‘ancilla’ qubits and Pauli Z-gates (see yellow circle around ‚Error correction‘ above):

Define

where |ψ1> = a|000> + b|111> is an eigenstate of both with eigenvalues +1; they ‘stabilize’ the quantum state

Stabilizers form an abelian group S and each stabilizer has eigenvalue +1 or -1, hence

where I being the identitiy matrix, leaving the quantum state unchanged (except for a global phase, not relevant for measurements). With 

Example: q1 flipped, hence e.g.

The correction code before doesn’t help with phase flips (arising, because quantum states are continuous, in contrast to classical bits): assume  a|0> + b|1> has been encoded, then a phase flip error occurs:  (Z ⨂ I ⨂ I) (a|000> + b|111>) = a|000> – b|111>. This would be exactly the state if starting with a|0> – b|1>, so how to identify its errorous?

A phase flip is |+>  ->  |-> or vice versa, hence with the following circuit: 

|ψ> = a|0> + b|1>  ->  a|000> + b|111>  ->  a|+++> + b|—>

To correct a phase error:

2.  Correcting an arbitrary single qubit error

The ‘error-space’ is continuous (e.g. due to noise). But: as long as it is possible to correct a bit-flip, a phase-flip, or both, correcting an arbitrary single-qubit unitary error is also possible!

To show this, first note:

• The results of measuring the parity qubits (S1, S2) is called syndrome, e.g. for a bit flip error: 

• All quantum operations are unitary. Why? Recall: Quantum systems are represented as vectors in a finite dimensional Hilbert space H; the state evolution is described by the Schrödinger equation. Observables are measurable quantities represented by Hermitian operators A є B(H), where B(H) are all bounded linear operations on H. Now: any evolution operator must be linear (because applying A to a state represented by a complex vector must result in a complex vector in H!) and length-preserving (since the total probability has to remain 1!), i.e. T: B(H) -> B(H) with tr(XY) = tr(T(X)T(Y)) for all X,Y in B(H). In other words, T can rotate the state vector anywhere within H, preserving the length. This is the geometric definition of a unitary matrix!

With that, shown next: The measurement of the syndrome projects any quantum error onto one of 4 possible errors, which can be corrected

Up to now: any single qubit error of the form (Y = ZX)

can be corrected (called Pauli errors: Pauli matrices form a basis for all 2×2 complex matrices!)

Now: let A be an arbitrary complex (unitary) matrix. Then there are a, b, c, d є C, so that  A = a I + b X + c Y + d Z. For the jth qubit of an n qubit state:

Measuring the syndrome (not altering the original state and collapsing any superposition of different errors states into one of the four states!) gives

After identifying by the syndrome which ‘Pauli’ error to which qubit happened, applying the correction code is just multiplying it with the corresponding Pauli operator again (since the same Pauli operator applied twice gives the identity matrix), which then recovers |ψ>:  

3. Sources

[1] Quantum Computation and Quantum Information, Nielsen, Chuang, Cambridge University Press

1. Decoherence
2. Noise
3. Neutral Atom Quantum Computer & Rydberg Atoms [1], [2]
4. The Need for Quantum Error Correction
5. Sources

1. Decoherence

Quantum states are very easily damaged by uncontrolled interactions with the environment

In addition, a quantum state decays from a higher energy state |1> to the ground state |0> := coherence time, i.e. how long is a quantum state stable?

T1 describes ‘how long does a qubit stay close to |1>‘

– this is, why we never see macroscopic superposition, like a dead cat which is alive 😊

The coherence time must be much longer than the (quantum) gate operation time. Since decoherence cannot be avoided: fault tolerance and error correction is unavoidable!

Some other error sources:

• Ability to initialize qubits reliable
• Reliable measurement capability (e.g. for the ancilla qubits, see the stabilizer blog)

2. Noise

Noise corresponds to a phase coherence time, e.g. in the xy-plane of the Bloch sphere:

But in reality: after the Hadamar Gate, there will be drifting in the xy-plane by some small φ and hence it is not exactly the orthogonal basis state anymore!   

Note: Noise is not a unitary transformation,

Noise is superpositioning decoherence!

3. Neutral Atom Quantum Computer & Rydberg  Atoms [1], [2]

There are various architectures to build a quantum computer, none currently able to support the quantum advantage on a broader scale (due to scaling and stabilitiy issues, resulting in a very short available computational time). Here an approach followed e.g. by Atom Computing is looked into, using neutral atoms trapped with highly focused laser beams (in contrast, IBM is using tiny superconducting circuits to realize qubits, see e.g. [3])

In general, DiVincenzo’s criteria describe a guideline for building a quantum computer [4]:

1. Well-characterized and scalable qubits
2. Qubit initialization
3. Long coherence times
4. Universal set of gates to perform operations on qubits
5. Measurement of individual qubits

Optical tweezers can trap a neutral atom (essentially because on very small scales the atom is not really neutral, and a laser beam is an electromagnetic wave, i.e. oscillating electric and magnetic fields, interacting with the electrons of the ‘neutral’ atom)

Rydberg atoms have large electrical dipole moments compared to ground state atoms and hence strong interactions with external fields (macroscopic) or electromagnetic fields from nearby particles (microscopic) [5]. These interactions can be controlled e.g. by lasers or microwaves, making neutral Rydberg atoms a reasonable choice for qubit-registers. In a circular Rydberg atom, the excited electron follows a (large)  circular path around the atomic nucleus, leading to a longer lifetime. Strontium is an example:  τ0 = 2,55 ms (T1 from before) at room temperature, [6]!

To encode a qubit in a neutral atom, one needs to have access to two distinct atomic quantum states, hence try to switch a single electron between energy states. Ideal are atoms with one valence electron (for more details on atom’s energy levels and electrons see e.g. [7]).

Having chosen one electron in the atom it has to be ensured, that only two energy levels are in play forming a qubit! One of the energy levels will be a ground state for the valence electron, called fiducial state, denoted by |0>. The other energy level will be a long-living excited state, called the hyperfine state, denoted |1>. The transition between those to energy levels will be induced by light whose energy is exactly the energy difference between these two atomic levels.

Now DiVincenzo’s second criteria: all qubits of a register need to be initialized to the fiducial ground state. This state is stable, since minimal-energy states will not spontaneously emit any energy. For Rb-85 atoms this can be achieved by laser cooling, see [8], Nobel Price in Physics 1997. Rb-85, because it has only one valence electron and in addition two (degenerated, same minimal energy level) ground states |0> and |0’> which can be excited to |1> and |1’>. But from both excited states the prefered fall back is |0>, the fiducial ground state. Together with optical tweezers so focused to allow at most a single atom trapped, the RB-85 atoms can be initialized and arranged as needed.

There are two additional issues: the trap has at most one atom, so some are empty, and laser cooling incorporates probabilities, so not all Rb-85 are in the |0> state. By exciting the atoms with photons having exact the right energy to bring the Rb-85 atoms to some short-lived excited state, the resulting decay to |0> will emit photons identifying the atoms in |0>

To do computations, the energy levels (quantum states) involving the valence electron needs to be controlled over time. This is achieved by short light pulses with specific amplitudes and phases. Not going into mathematical details, the observable energy levels as the quantum state’s evolvement in time is described by the Hamiltonian H of the system, see e.g. [7].

( In general Schrödinger’s equation looks like 

which looks a lot easier then it is …😊)

It can be shown, [9]: the Blackman window pulse is appropriate to be applied to all the Rb-85 atoms in the array in question.

It turns out: e.g. the one-qubit rotation gate 

can be realized by a Blackman pulse of amplitude 

Analogously: Ry

What about two-qubit gates, adding qubit interactions? Although the atoms are neutral, Van der Waals interactions will occur on small scales between (Rydberg) atoms. Define next to the ground state the second used (high energy) quantum state of a Rydberg atom as Rydberg state |r>. If two atoms are ‘far’ away two energy pulses can lead to |00> -> |0r> -> |rr>. But when the distance becomes too small, only |0r> or |r0> can occur. This is called the Rydberg blockade. But because of this blockade, the quantum gate

can be defined, providing together with the other two a universal set of gates

The Rz gate can be realized with two atoms (control and target), the Rydberg blockade and the following three pulses in this specific order:

This leads to

•  |00> -> -|00>

|00>: The first π pulse brings |00> -> |r0>, the 2π pulse (target qubit) to |rr> and further to |r0> again is suppressed because of the blockade and the second π pulse rotates the control qubit further to its original state; all following transitions: the π and 2π pulses do not correspond to the energy level of |1> -> |r>

•  |01> -> -|01>
•  |01> -> -|01>
•  |11> -> |11>

Up to a global phase, this is the Rz gate!

But in practice: It is not easy to address single atoms with laser pulses. In addition: decoherence times and external interactions (no perfect vacuum) destroys the arranged quantum states (the Rydberg states) very quickly, leading as mentioned to issues regarding scalability and computational time

Hence Quantum Error Correction …

4. The Need for Quantum Error Correction

Possible ‘spontaneous’ errors:

• Bit flip: a|0> + b|1> -> b|0> + a|1>  (on purpose: X-gate)
• Phase error (with no classical counterpart): a|0> + b|1> -> a|0> – b|1> (Z-gate)

Since there is the no cloning theorem of quantum states, e.g. [10], and hence no classical storage (RAM-) duplicating is possible, another approach is necessary. Based on entanglement, this is QEC (Quantum Error Correction)

A logical qubit is an abstract, error-protected qubit that is encoded across many physical qubits. Spreading information across several physical qubits by entanglement, errors can be detected and corrected, [11]

Correct any single qubit error (flip and/or phase): 9 qubit Shor code (see the corresponding blog)

I.e. in general, for n stable and corrected (logical) qubits, 9n physical qubits are needed

But with this approach: to correct errors of qubits, one needs more qubits, and then more qubits to correct the error-correcting qubits! Nevertheless, one can calculate a threshold [12] (and the following blogs on the surface code)

5. Sources

• [1] ‚Neutral-atom quantum computer‘ by Alvaro Ballon, 2023 (pennylane.ai/qml/demos/tutorial_neutral_atoms)
• [2] ‚Quantum Computing With Neutral Atoms‘ by Henriet et al., 2020  (arxiv.org/pdf/2006.12326) 
• [3] ‚A Quantum Engineer’s Guide To Superconducting Qubits‘ by Krantz et al., 2021  (arxiv.org/pdf/1904.06560)
• [4] ‚The Physical Implementation of Quantum Computation‘ by DiVincenzo, 2000  (arxiv.org/pdf/quant-ph/0002077)
• [5] ‚A concise review of Rydberg atom based quantum computation and quantum simulation‘ by Wu et al., 2021  (arxiv.org/pdf/2012.10614)
• [6] ‚Long-Lived Circular Rydberg Qubits of Alkaline-Earth Atoms in Optical Tweezers‘ by Hölzl et al., 2024  (journals.aps.org/prx/abstract/10.1103/PhysRevX.14.021024)
• [7] Vorlesungen über Physik, Band III: Quantenmechanik, Feynman/Leighton/Sands, Oldenbourg, 2.Aufl. 1992
• [8] ‚Laser Cooling and Trapping of Neutral Atoms‘ by Phillips, 1997 (nobelprize.org/uploads/2018/06/phillips-lecture.pdf)
• [9] ‚Pulser: An open-source package for the design of pulse sequences in programmable neutral-atom arrays‘  by Silvério et al., 2022  (arxiv.org/pdf/2104.15044)
• [10] ‚Limitations on quantum information‘ by IBM Learning (quantum.cloud.ibm.com/learning/en/courses/basics-of-quantum-information/quantum-circuits/limitations-on-quantum-information)
• [11] ‚The Rise of Logical Qubits: How Quantum Computers Fight Errors‘ by Ivezic, 2025  (postquantum.com/quantum-computing/logical-qubits/)
• [12] ‚Suppressing quantum errors by scaling a surface code logical qubit‘ by Google Quantum AI, 2022  (arxiv.org/pdf/2207.06431)