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]:

upb_ss1

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

upb_ss2

The output of the script in this case can be read as follows. On the orthogonality graph for party P1, there is a shaded region containing vertices v0 and v1, another shaded region containing vertices v2 and v3, and another shaded region containing vertices v4 and v5. On the orthogonality graph for party P2, there is a shaded region containing vertices v0 and v3, another shaded region containing vertices v1 and v4, and another shaded region containing vertices v2 and v5. Parties P3 and P4 are similar.

If we wish to enforce the fact that every shaded region containing 2 vertices contains at least one of three fixed vertices v0, v2, v4 (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:

upb_ss3

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

  1. 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
  1. No comments yet.
  1. No trackbacks yet.