If the boundary has no corners, $N$ holes turn out to be sufficient as long as they match the boundary type. Finally, with $N+1$ holes of the same type, all logical operators on $N$ logical qubits may be obtained from chains going around the holes and linking holes to each other andso the boundary may be ignored. This is a consequence of the fact that pair-of-holes encoding allows different logical qubits to share one of the holes.
This answer provides a "combinatorial" approach to computing the dimension of the logical subspace and is meant to complement the "topological" approach described in Craig Gidney's answer.
Importance of generator independence
Our starting point is the fact that a stabilizer group $S$ on $n$ physical qubits generated by $g$ independent generators stabilizes a $2^{n-g}$-dimensional subspace. See for example proposition $10.5$ on page $458$ in Nielsen & Chuang. This fact supports the general rule alluded to in the question that removing one of the independent generators adds a logical qubit.
The surface code is a stabilizer code so the above rule applies. However, careless application of the rule may lead to the incorrect conclusion that punching a hole in the surface code always adds a logical qubit. This is only true if the generator removed is independent of the other generators. For example, the $Z_c$ generator at the center of the code pictured below
is easily seen to be equal to the product of all the other $Z$ (dark) generators and therefore is not independent. Consequently, removing $Z_c$ fails to introduce a degree of freedom necessary for the formation of a logical qubit.
Topological interpretation
This fact has a topological interpretation. Note that the hole formed by the removal of $Z_c$ has boundary type opposite to the outer boundary of the code. Therefore, it is impossible to find two anti-commuting logical observables, as described in Craig's answer.
Planar codes with two or more corners
It turns out that in a planar hole-free surface code all plaquettes correspond to independent generators if and only if the code has at least two corners defined here as data qubits incident on exactly two stabilizer generators (one of each type). Such a code possesses at least one boundary of each type. Introducing a pair of corners is associated with the net loss of one independent stabilizer generator. Therefore, a planar hole-free surface code with $c\ge 2$ corners encodes
$$ k=\frac{c-2}{2}\tag1 $$
logical qubits. Moreover, removal of any generator from the bulk (so that the number of corners is unaffected) is associated with the loss of a single independent generator. Therefore, a planar surface code with $c\ge 2$ corners and $h$ bulk generators removed encodes
$$ k = h + \frac{c-2}{2}\tag2 $$
logical qubits. The effect of punching a hole larger than a single plaquette depends on the number of removed generators and data qubits, but it is possible to punch a hole of any size while removing $d$$q$ data qubits and $d+1$$q+1$ generators leading to the introduction of exactly one degree of freedom.
Dimension of the logical subspace
In this example we then only use $2$ dimensions out of the $2^3$ conceptually available (one logical qubit out of the three conceptually available). Is that correct?
Depends on the boundary. By equation $(2)$, the answer is yes if we assume for example assume that the boundary includes four corners, i.e. the code has two boundaries of each type.
If we want to add logical qubits, we create more pair of holes. Hence for $N$ logical qubits that we want to store, we will create $N$ pairs of holes on the surface. Conceptually we could store $2N+1$ logical qubits with this construction but we will only manipulate $N$ out of them. Is that correct?
Yes, but this is wasteful. By equation $(2)$, if the boundary has two corners, $N$ holes are sufficient. If the boundary has no corners, we need $N+1$ holes.
This answer provides a "combinatorial" approach to computing the dimension of the logical subspace and is meant to complement the "topological" approach described in Craig Gidney's answer.
Importance of generator independence
Our starting point is the fact that a stabilizer group $S$ on $n$ physical qubits generated by $g$ independent generators stabilizes a $2^{n-g}$-dimensional subspace. See for example proposition $10.5$ on page $458$ in Nielsen & Chuang. This fact supports the general rule alluded to in the question that removing one of the independent generators adds a logical qubit.
The surface code is a stabilizer code so the above rule applies. However, careless application of the rule may lead to the incorrect conclusion that punching a hole in the surface code always adds a logical qubit. This is only true if the generator removed is independent of the other generators. For example, the $Z_c$ generator at the center of the code pictured below
is easily seen to be equal to the product of all the other $Z$ (dark) generators and therefore is not independent. Consequently, removing $Z_c$ fails to introduce a degree of freedom necessary for the formation of a logical qubit.
Topological interpretation
This fact has a topological interpretation. Note that the hole formed by the removal of $Z_c$ has boundary type opposite to the outer boundary of the code. Therefore, it is impossible to find two anti-commuting logical observables, as described in Craig's answer.
Planar codes with two or more corners
It turns out that in a planar hole-free surface code all plaquettes correspond to independent generators if and only if the code has at least two corners defined here as data qubits incident on exactly two stabilizer generators (one of each type). Such a code possesses at least one boundary of each type. Introducing a pair of corners is associated with the net loss of one independent stabilizer generator. Therefore, a planar hole-free surface code with $c\ge 2$ corners encodes
$$ k=\frac{c-2}{2}\tag1 $$
logical qubits. Moreover, removal of any generator from the bulk (so that the number of corners is unaffected) is associated with the loss of a single independent generator. Therefore, a planar surface code with $c\ge 2$ corners and $h$ bulk generators removed encodes
$$ k = h + \frac{c-2}{2}\tag2 $$
logical qubits. The effect of punching a hole larger than a single plaquette depends on the number of removed generators and data qubits, but it is possible to punch a hole of any size while removing $d$ data qubits and $d+1$ generators leading to the introduction of exactly one degree of freedom.
Dimension of the logical subspace
In this example we then only use $2$ dimensions out of the $2^3$ conceptually available (one logical qubit out of the three conceptually available). Is that correct?
Depends on the boundary. By equation $(2)$, the answer is yes if we for example assume that the boundary includes four corners, i.e. two boundaries of each type.
If we want to add logical qubits, we create more pair of holes. Hence for $N$ logical qubits that we want to store, we will create $N$ pairs of holes on the surface. Conceptually we could store $2N+1$ logical qubits with this construction but we will only manipulate $N$ out of them. Is that correct?
Yes, but this is wasteful. By equation $(2)$, if the boundary has two corners, $N$ holes are sufficient. If the boundary has no corners, we need $N+1$ holes.
This answer provides a "combinatorial" approach to computing the dimension of the logical subspace and is meant to complement the "topological" approach described in Craig Gidney's answer.
Importance of generator independence
Our starting point is the fact that a stabilizer group $S$ on $n$ physical qubits generated by $g$ independent generators stabilizes a $2^{n-g}$-dimensional subspace. See for example proposition $10.5$ on page $458$ in Nielsen & Chuang. This fact supports the general rule alluded to in the question that removing one of the independent generators adds a logical qubit.
The surface code is a stabilizer code so the above rule applies. However, careless application of the rule may lead to the incorrect conclusion that punching a hole in the surface code always adds a logical qubit. This is only true if the generator removed is independent of the other generators. For example, the $Z_c$ generator at the center of the code pictured below
is easily seen to be equal to the product of all the other $Z$ (dark) generators and therefore is not independent. Consequently, removing $Z_c$ fails to introduce a degree of freedom necessary for the formation of a logical qubit.
Topological interpretation
This fact has a topological interpretation. Note that the hole formed by the removal of $Z_c$ has boundary type opposite to the outer boundary of the code. Therefore, it is impossible to find two anti-commuting logical observables, as described in Craig's answer.
Planar codes with two or more corners
It turns out that in a planar hole-free surface code all plaquettes correspond to independent generators if and only if the code has at least two corners defined here as data qubits incident on exactly two stabilizer generators (one of each type). Such a code possesses at least one boundary of each type. Introducing a pair of corners is associated with the net loss of one independent stabilizer generator. Therefore, a planar hole-free surface code with $c\ge 2$ corners encodes
$$ k=\frac{c-2}{2}\tag1 $$
logical qubits. Moreover, removal of any generator from the bulk (so that the number of corners is unaffected) is associated with the loss of a single independent generator. Therefore, a planar surface code with $c\ge 2$ corners and $h$ bulk generators removed encodes
$$ k = h + \frac{c-2}{2}\tag2 $$
logical qubits. The effect of punching a hole larger than a single plaquette depends on the number of removed generators and data qubits, but it is possible to punch a hole of any size while removing $q$ data qubits and $q+1$ generators leading to the introduction of exactly one degree of freedom.
Dimension of the logical subspace
In this example we then only use $2$ dimensions out of the $2^3$ conceptually available (one logical qubit out of the three conceptually available). Is that correct?
Depends on the boundary. By equation $(2)$, the answer is yes if we assume for example that the boundary includes four corners, i.e. the code has two boundaries of each type.
If we want to add logical qubits, we create more pair of holes. Hence for $N$ logical qubits that we want to store, we will create $N$ pairs of holes on the surface. Conceptually we could store $2N+1$ logical qubits with this construction but we will only manipulate $N$ out of them. Is that correct?
Yes, but this is wasteful. By equation $(2)$, if the boundary has two corners, $N$ holes are sufficient. If the boundary has no corners, we need $N+1$ holes.