## Code for proving that no UPB of size 4k+3 exists on 4k qubits

This page contains C code that is used to fill in some gaps in the proof of Lemma 6 of [1] and hence prove that there is no unextendible product basis consisting of exactly 4k+3 vectors on 4k qubits when k ≥ 3.

### Download

**Step 1:** Download the QubitUPBSearch.c file (file size: 9 kB).

**Step 2:** Compile and run the script (if you don’t know if you have a C compiler or how to install a compiler, it may be easiest to download and install CodeBlocks).

### Usage

The script is hopefully straightforward to use, as it prompts you and asks you which search you want to carry out. For example, the following screenshot shows the script confirming that there is no way to arrange 3 sets of 2 equal states on 5 parties without violating unextendibility, a fact that is made use of in case 3(b) of the proof of Lemma 6 of [1]:

Similarly, to see that there *are* ways to arrange 3 sets of 2 equal states on 4 parties without violating unextendibility:

The output of the script in this case can be read as follows. On the orthogonality graph for party P_{1}, there is a shaded region containing vertices v_{0} and v_{1}, another shaded region containing vertices v_{2} and v_{3}, and another shaded region containing vertices v_{4} and v_{5}. On the orthogonality graph for party P_{2}, there is a shaded region containing vertices v_{0} and v_{3}, another shaded region containing vertices v_{1} and v_{4}, and another shaded region containing vertices v_{2} and v_{5}. Parties P_{3} and P_{4} are similar.

If we wish to enforce the fact that every shaded region containing 2 vertices contains at least one of three fixed vertices v_{0}, v_{2}, v_{4} (which is used in case 4 of the proof of Lemma 6 of [1]), then enter “1” at the second prompt. We see that there is no way to have 3 or more parties when this additional restriction is in effect:

Note that the output of the script is only valid if s ≥ 3, since the unextendibility check used does not know how to deal with s < 3 case.

### References

- N. Johnston. The minimum size of qubit unextendible product bases. In
*Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)*, 2013. doi: 10.4230/LIPIcs.TQC.2013.93