As mentioned on the home page, the number of nuggets grows quickly as the number of qubits in a qureg increases. This page talks about how to shorten the calculation of naïve entanglement in a way that minimally affects the accuracy of the result. Demonstrated are some options with an example qureg of four qubits. Full evaluation would incur 112 nuggets, which can be placed into three categories (tables 1, 2 and 3, but not 4, which all appear below) according to how many times products of particular amplitudes are computed.
It will be useful to think of the index numbers as though written in binary, and thence interpret them as bit strings. For instance, 14_{10} = 1110_{2} and 9_{10} = 1001_{2}. Then the boolean operations AND and OR can be performed on them bit by bit. For instance:
AND | OR | |
---|---|---|
in decimal: | 14 AND 9 = 8 | 14 OR 9 = 15 |
in binary: | 1110 AND 1001 = 1000 | 1110 OR 1001 = 1111 |
Table 1 displays all 24 nuggets where, if i and j are viewed as binary numbers, they differ in exactly two bit positions within any product c_{i} × c_{j}.
These happen to be the same as the nuggets that would be counted twice in the full naïve measure. When that duplication is eliminated, no product c_{i} × c_{j} appears more than once. To make the pattern clearer, the table has been arranged so that each amplitude appears once in each row.
Table 1. | |||
---|---|---|---|
│ c_{0} × c_{3} − c_{1} × c_{2} │ | │ c_{4} × c_{7} − c_{5} × c_{6} │ | │ c_{8} × c_{11} − c_{9} × c_{10} │ | │ c_{12} × c_{15} − c_{13} × c_{14} │ |
│ c_{0} × c_{5} − c_{1} × c_{4} │ | │ c_{2} × c_{7} − c_{3} × c_{6} │ | │ c_{8} × c_{13} − c_{9} × c_{12} │ | │ c_{10} × c_{15} − c_{11} × c_{14} │ |
│ c_{0} × c_{6} − c_{2} × c_{4} │ | │ c_{1} × c_{7} − c_{3} × c_{5} │ | │ c_{8} × c_{14} − c_{10} × c_{12} │ | │ c_{9} × c_{15} − c_{11} × c_{13} │ |
│ c_{0} × c_{9} − c_{1} × c_{8} │ | │ c_{2} × c_{11} − c_{3} × c_{10} │ | │ c_{4} × c_{13} − c_{5} × c_{12} │ | │ c_{6} × c_{15} − c_{7} × c_{14} │ |
│ c_{0} × c_{10} − c_{2} × c_{8} │ | │ c_{1} × c_{11} − c_{3} × c_{9} │ | │ c_{4} × c_{14} − c_{6} × c_{12} │ | │ c_{5} × c_{15} − c_{7} × c_{13} │ |
│ c_{0} × c_{12} − c_{4} × c_{8} │ | │ c_{1} × c_{13} − c_{5} × c_{9} │ | │ c_{2} × c_{14} − c_{6} × c_{10} │ | │ c_{3} × c_{15} − c_{7} × c_{11} │ |
As in the full case, this briefer naïve measurement of entanglement would incur taking the square root of the sum of the squares of all these nuggets.
Table 1 does not have algebraic symmetry, in that the amplitudes cannot be permuted at will. However, we will say the the aggregate of formulas is balanced, because the measure is unchanged when:
Table 2 displays the 48 nuggets where i and j differ in exactly three bit positions within any product c_{i} × c_{j}. Each product occurs exactly three times. The set of nuggets is partitionable into subsets that involve only four products; they are displayed one subset per row.
Table 2. | |||||
---|---|---|---|---|---|
│ c_{0} × c_{7} − c_{1} × c_{6} │ | │ c_{0} × c_{7} − c_{2} × c_{5} │ | │ c_{0} × c_{7} − c_{3} × c_{4} │ | │ c_{1} × c_{6} − c_{2} × c_{5} │ | │ c_{1} × c_{6} − c_{3} × c_{4} │ | │ c_{2} × c_{5} − c_{3} × c_{4} │ |
│ c_{0} × c_{11} − c_{1} × c_{10} │ | │ c_{0} × c_{11} − c_{2} × c_{9} │ | │ c_{0} × c_{11} − c_{3} × c_{8} │ | │ c_{1} × c_{10} − c_{2} × c_{9} │ | │ c_{1} × c_{10} − c_{3} × c_{8} │ | │ c_{2} × c_{9} − c_{3} × c_{8} │ |
│ c_{0} × c_{13} − c_{1} × c_{12} │ | │ c_{0} × c_{13} − c_{4} × c_{9} │ | │ c_{0} × c_{13} − c_{5} × c_{8} │ | │ c_{1} × c_{12} − c_{4} × c_{9} │ | │ c_{1} × c_{12} − c_{5} × c_{8} │ | │ c_{4} × c_{9} − c_{5} × c_{8} │ |
│ c_{0} × c_{14} − c_{2} × c_{12} │ | │ c_{0} × c_{14} − c_{4} × c_{10} │ | │ c_{0} × c_{14} − c_{6} × c_{8} │ | │ c_{2} × c_{12} − c_{4} × c_{10} │ | │ c_{2} × c_{12} − c_{6} × c_{8} │ | │ c_{4} × c_{10} − c_{6} × c_{8} │ |
│ c_{1} × c_{15} − c_{3} × c_{13} │ | │ c_{1} × c_{15} − c_{5} × c_{11} │ | │ c_{1} × c_{15} − c_{7} × c_{9} │ | │ c_{3} × c_{13} − c_{5} × c_{11} │ | │ c_{3} × c_{13} − c_{7} × c_{9} │ | │ c_{5} × c_{11} − c_{7} × c_{9} │ |
│ c_{2} × c_{15} − c_{3} × c_{14} │ | │ c_{2} × c_{15} − c_{6} × c_{11} │ | │ c_{2} × c_{15} − c_{7} × c_{10} │ | │ c_{3} × c_{14} − c_{6} × c_{11} │ | │ c_{3} × c_{14} − c_{7} × c_{10} │ | │ c_{6} × c_{11} − c_{7} × c_{10} │ |
│ c_{4} × c_{15} − c_{5} × c_{14} │ | │ c_{4} × c_{15} − c_{6} × c_{13} │ | │ c_{4} × c_{15} − c_{7} × c_{12} │ | │ c_{5} × c_{14} − c_{6} × c_{13} │ | │ c_{5} × c_{14} − c_{7} × c_{12} │ | │ c_{6} × c_{13} − c_{7} × c_{12} │ |
│ c_{8} × c_{15} − c_{9} × c_{14} │ | │ c_{8} × c_{15} − c_{10} × c_{13} │ | │ c_{8} × c_{15} − c_{11} × c_{12} │ | │ c_{9} × c_{14} − c_{10} × c_{13} │ | │ c_{9} × c_{14} − c_{11} × c_{12} │ | │ c_{10} × c_{13} − c_{11} × c_{12} │ |
As with table 1, the nuggets of table 2 are balanced.
Table 3 displays the 16 nuggets where i and j differ in exactly four bit positions within any product; each product occurs exactly four times. For any two products c_{i} × c_{j} and c_{k} × c_{l}, we can say if i = k then j = l and conversely.
Table 3. | |||
---|---|---|---|
│ c_{0} × c_{15} − c_{1} × c_{14} │ | │ c_{0} × c_{15} − c_{2} × c_{13} │ | │ c_{0} × c_{15} − c_{4} × c_{11} │ | │ c_{0} × c_{15} − c_{7} × c_{8} │ |
│ c_{1} × c_{14} − c_{3} × c_{12} │ | │ c_{1} × c_{14} − c_{5} × c_{10} │ | │ c_{1} × c_{14} − c_{6} × c_{9} │ | │ c_{2} × c_{13} − c_{3} × c_{12} │ |
│ c_{2} × c_{13} − c_{5} × c_{10} │ | │ c_{2} × c_{13} − c_{6} × c_{9} │ | │ c_{3} × c_{12} − c_{4} × c_{11} │ | │ c_{3} × c_{12} − c_{7} × c_{8} │ |
│ c_{4} × c_{11} − c_{5} × c_{10} │ | │ c_{4} × c_{11} − c_{6} × c_{9} │ | │ c_{5} × c_{10} − c_{7} × c_{8} │ | │ c_{6} × c_{9} − c_{7} × c_{8} │ |
These nuggets are balanced.
We can extend this. In a non-entangled qureg, c_{i} × c_{j} will equal c_{k} × c_{l} if two conditions are met, namely
Table 4 shows the twelve additional nuggets (balanced, but not part of naïve entanglement) that are generated when these conditions are satisfied:
Table 4. | |||
---|---|---|---|
│ c_{0} × c_{15} − c_{3} × c_{12} │ | │ c_{0} × c_{15} − c_{5} × c_{10} │ | │ c_{0} × c_{15} − c_{6} × c_{9} │ | │ c_{1} × c_{14} − c_{2} × c_{3} │ |
│ c_{1} × c_{14} − c_{4} × c_{11} │ | │ c_{1} × c_{14} − c_{7} × c_{8} │ | │ c_{2} × c_{13} − c_{4} × c_{11} │ | │ c_{2} × c_{13} − c_{7} × c_{8} │ |
│ c_{3} × c_{12} − c_{5} × c_{10} │ | │ c_{3} × c_{12} − c_{6} × c_{9} │ | │ c_{4} × c_{11} − c_{7} × c_{8} │ | │ c_{5} × c_{10} − c_{6} × c_{9} │ |
These would naturally fit as an extension to table 3.
Several ways to take a balanced subset of nuggets are shown above. Is one better than another?
A weakness of the subset displayed in table 3 is that when, for instance, c_{2} appears it is always multiplied by c_{13}. It is easy to contrive an example where each of c_{2} and c_{13} contribute to entangement, but where the evidence of it is lost when they are multiplied. We call this a lack of variegation. Appending the contents of table 4 does not help.
Table 2 does better, as each amplitude is multiplied by four other amplitudes, but each product is still used four times. Table 1 goes further, each amplitude being multiplied by six other amplitudes, and no product ever being reused. With all this variegation, the chances are greatly increased that any entanglement will be detected, so we recommend the two-bit-difference standard of table 1.
So much for the case where a qureg has 4 qubits. For a qureg with n qubits, the quantity of nuggets with two-bit difference (as in table 1) is C (n, 2) × 2^{n−2} where C is the combination function.
More broadly, the quantity of nuggets with a b-bit difference is C (n, b) × 2^{n−b}. This figure is O(2^{n}) (see big O notation) in contrast to the quantity of all nuggets, which is O(4^{n}). The former is the square root of the latter, and is thus considerably smaller for large n; this difference may be critical to the feasibility of some computations.
As a concrete example, we list the nuggets for a 5-qubit register where i and j differ in exactly two bit positions within any product c_{i} × c_{j}, analogous to table 1. Table 5 is arranged so that each amplitude appears once in each (double) row.
Table 5. | ||||
---|---|---|---|---|
Row 0 | │ c_{0} × c_{3} − c_{1} × c_{2} │ | │ c_{4} × c_{7} − c_{5} × c_{6} │ | │ c_{8} × c_{11} − c_{9} × c_{10} │ | │ c_{12} × c_{15} − c_{13} × c_{14} │ |
│ c_{16} × c_{19} − c_{17} × c_{18} │ | │ c_{20} × c_{23} − c_{21} × c_{22} │ | │ c_{24} × c_{27} − c_{25} × c_{26} │ | │ c_{28} × c_{31} − c_{29} × c_{30} │ | |
Row 1 | │ c_{0} × c_{5} − c_{1} × c_{4} │ | │ c_{2} × c_{7} − c_{3} × c_{6} │ | │ c_{8} × c_{13} − c_{9} × c_{12} │ | │ c_{10} × c_{15} − c_{11} × c_{14} │ |
│ c_{16} × c_{21} − c_{17} × c_{20} │ | │ c_{18} × c_{23} − c_{19} × c_{22} │ | │ c_{24} × c_{29} − c_{25} × c_{28} │ | │ c_{26} × c_{31} − c_{27} × c_{30} │ | |
Row 2 | │ c_{0} × c_{6} − c_{2} × c_{4} │ | │ c_{1} × c_{7} − c_{3} × c_{5} │ | │ c_{8} × c_{14} − c_{10} × c_{12} │ | │ c_{9} × c_{15} − c_{11} × c_{13} │ |
│ c_{16} × c_{22} − c_{18} × c_{20} │ | │ c_{17} × c_{23} − c_{19} × c_{21} │ | │ c_{24} × c_{30} − c_{26} × c_{28} │ | │ c_{25} × c_{31} − c_{27} × c_{29} │ | |
Row 3 | │ c_{0} × c_{9} − c_{1} × c_{8} │ | │ c_{2} × c_{11} − c_{3} × c_{10} │ | │ c_{4} × c_{13} − c_{5} × c_{12} │ | │ c_{6} × c_{15} − c_{7} × c_{14} │ |
│ c_{16} × c_{25} − c_{17} × c_{24} │ | │ c_{18} × c_{27} − c_{19} × c_{26} │ | │ c_{20} × c_{29} − c_{21} × c_{28} │ | │ c_{22} × c_{31} − c_{23} × c_{30} │ | |
Row 4 | │ c_{0} × c_{10} − c_{2} × c_{8} │ | │ c_{1} × c_{11} − c_{3} × c_{9} │ | │ c_{4} × c_{14} − c_{6} × c_{12} │ | │ c_{5} × c_{15} − c_{7} × c_{13} │ |
│ c_{16} × c_{26} − c_{18} × c_{24} │ | │ c_{17} × c_{27} − c_{19} × c_{25} │ | │ c_{20} × c_{30} − c_{22} × c_{28} │ | │ c_{21} × c_{31} − c_{23} × c_{29} │ | |
Row 5 | │ c_{0} × c_{12} − c_{4} × c_{8} │ | │ c_{1} × c_{13} − c_{5} × c_{9} │ | │ c_{2} × c_{14} − c_{6} × c_{10} │ | │ c_{3} × c_{15} − c_{7} × c_{11} │ |
│ c_{16} × c_{28} − c_{20} × c_{24} │ | │ c_{17} × c_{29} − c_{21} × c_{25} │ | │ c_{18} × c_{30} − c_{22} × c_{26} │ | │ c_{19} × c_{31} − c_{23} × c_{27} │ | |
Row 6 | │ c_{0} × c_{17} − c_{1} × c_{16} │ | │ c_{2} × c_{19} − c_{3} × c_{18} │ | │ c_{4} × c_{21} − c_{5} × c_{20} │ | │ c_{6} × c_{23} − c_{7} × c_{22} │ |
│ c_{8} × c_{25} − c_{9} × c_{24} │ | │ c_{10} × c_{27} − c_{11} × c_{26} │ | │ c_{12} × c_{29} − c_{13} × c_{28} │ | │ c_{14} × c_{31} − c_{15} × c_{30} │ | |
Row 7 | │ c_{0} × c_{18} − c_{2} × c_{16} │ | │ c_{1} × c_{19} − c_{3} × c_{17} │ | │ c_{4} × c_{22} − c_{6} × c_{20} │ | │ c_{5} × c_{23} − c_{7} × c_{21} │ |
│ c_{8} × c_{26} − c_{10} × c_{24} │ | │ c_{9} × c_{27} − c_{11} × c_{25} │ | │ c_{12} × c_{30} − c_{14} × c_{28} │ | │ c_{13} × c_{31} − c_{15} × c_{29} │ | |
Row 8 | │ c_{0} × c_{20} − c_{4} × c_{16} │ | │ c_{1} × c_{21} − c_{5} × c_{17} │ | │ c_{2} × c_{22} − c_{6} × c_{18} │ | │ c_{3} × c_{23} − c_{7} × c_{19} │ |
│ c_{8} × c_{28} − c_{12} × c_{24} │ | │ c_{9} × c_{29} − c_{13} × c_{25} │ | │ c_{10} × c_{30} − c_{14} × c_{26} │ | │ c_{11} × c_{31} − c_{15} × c_{27} │ | |
Row 9 | │ c_{0} × c_{24} − c_{8} × c_{16} │ | │ c_{1} × c_{25} − c_{9} × c_{17} │ | │ c_{2} × c_{26} − c_{10} × c_{18} │ | │ c_{3} × c_{27} − c_{11} × c_{19} │ |
│ c_{4} × c_{28} − c_{12} × c_{20} │ | │ c_{5} × c_{29} − c_{13} × c_{21} │ | │ c_{6} × c_{30} − c_{14} × c_{22} │ | │ c_{7} × c_{31} − c_{15} × c_{23} │ |
The minimal number of nuggets needed to detect naïve entantanglement in a qureg of n qubits is 2^{n} − n − 1; a balanced selection is not always possible. Table 6 has examples of minimal sets for several n. Within each nugget the amplitude being checked for consistency with entanglement is rendered in boldface.
Table 6. | |||
---|---|---|---|
n ≥ 2 | n ≥ 3 | n ≥ 4 | n ≥ 5 |
│ c_{0} × c_{3} − c_{1} × c_{2} │ | │ c_{0} × c_{5} − c_{1} × c_{4} │ | │ c_{0} × c_{9} − c_{1} × c_{8} │ | │ c_{0} × c_{17} − c_{1} × c_{16} │ |
│ c_{0} × c_{6} − c_{2} × c_{4} │ | │ c_{0} × c_{10} − c_{2} × c_{8} │ | │ c_{0} × c_{18} − c_{2} × c_{16} │ | |
│ c_{1} × c_{7} − c_{3} × c_{5} │ | │ c_{1} × c_{11} − c_{3} × c_{9} │ | │ c_{1} × c_{19} − c_{3} × c_{17} │ | |
│ c_{0} × c_{12} − c_{4} × c_{8} │ | │ c_{0} × c_{20} − c_{4} × c_{16} │ | ||
│ c_{1} × c_{13} − c_{5} × c_{9} │ | │ c_{1} × c_{21} − c_{5} × c_{17} │ | ||
│ c_{2} × c_{14} − c_{6} × c_{10} │ | │ c_{2} × c_{22} − c_{6} × c_{18} │ | ||
│ c_{3} × c_{15} − c_{7} × c_{11} │ | │ c_{3} × c_{23} − c_{7} × c_{19} │ | ||
│ c_{0} × c_{24} − c_{8} × c_{16} │ | |||
│ c_{1} × c_{25} − c_{9} × c_{17} │ | |||
│ c_{2} × c_{26} − c_{10} × c_{18} │ | |||
│ c_{3} × c_{27} − c_{11} × c_{19} │ | |||
│ c_{4} × c_{28} − c_{12} × c_{20} │ | |||
│ c_{5} × c_{29} − c_{13} × c_{21} │ | |||
│ c_{6} × c_{30} − c_{14} × c_{22} │ | |||
│ c_{7} × c_{31} − c_{15} × c_{23} │ |
Here is the method for building an unentangled qureg that motivated the nugget choice above:
Adjusting the magnitude of the qureg to unity may be required after the amplitudes are established. Of course, multiplying all the amplitudes by the same constant will not induce any entanglement.