Home.

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, 1410 = 11102 and 910 = 10012. Then the boolean operations AND and OR can be performed on them bit by bit. For instance:

AND OR 14 AND 9 = 8 14 OR 9 = 15 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 ci × cj.

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 ci × cj 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.
c0 × c3c1 × c2c4 × c7c5 × c6c8 × c11c9 × c10c12 × c15c13 × c14
c0 × c5c1 × c4c2 × c7c3 × c6c8 × c13c9 × c12c10 × c15c11 × c14
c0 × c6c2 × c4c1 × c7c3 × c5c8 × c14c10 × c12c9 × c15c11 × c13
c0 × c9c1 × c8c2 × c11c3 × c10c4 × c13c5 × c12c6 × c15c7 × c14
c0 × c10c2 × c8c1 × c11c3 × c9c4 × c14c6 × c12c5 × c15c7 × c13
c0 × c12c4 × c8c1 × c13c5 × c9c2 × c14c6 × c10c3 × c15c7 × c11

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:

• the amplitudes corresponding to one qubit are exchanged with those of another qubit;
• the amplitudes corresponding to a qubit's boolean TRUE value are exchanged with those of the qubit's FALSE value.
Not surprisingly then, each amplitude appears the same number of times.

Table 2 displays the 48 nuggets where i and j differ in exactly three bit positions within any product ci × cj. 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.
c0 × c7c1 × c6c0 × c7c2 × c5c0 × c7c3 × c4c1 × c6c2 × c5c1 × c6c3 × c4c2 × c5c3 × c4
c0 × c11c1 × c10c0 × c11c2 × c9c0 × c11c3 × c8c1 × c10c2 × c9c1 × c10c3 × c8c2 × c9c3 × c8
c0 × c13c1 × c12c0 × c13c4 × c9c0 × c13c5 × c8c1 × c12c4 × c9c1 × c12c5 × c8c4 × c9c5 × c8
c0 × c14c2 × c12c0 × c14c4 × c10c0 × c14c6 × c8c2 × c12c4 × c10c2 × c12c6 × c8c4 × c10c6 × c8
c1 × c15c3 × c13c1 × c15c5 × c11c1 × c15c7 × c9c3 × c13c5 × c11c3 × c13c7 × c9c5 × c11c7 × c9
c2 × c15c3 × c14c2 × c15c6 × c11c2 × c15c7 × c10c3 × c14c6 × c11c3 × c14c7 × c10c6 × c11c7 × c10
c4 × c15c5 × c14c4 × c15c6 × c13c4 × c15c7 × c12c5 × c14c6 × c13c5 × c14c7 × c12c6 × c13c7 × c12
c8 × c15c9 × c14c8 × c15c10 × c13c8 × c15c11 × c12c9 × c14c10 × c13c9 × c14c11 × c12c10 × c13c11 × c12

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 ci × cj and ck × cl, we can say if i = k then j = l and conversely.

Table 3.
c0 × c15c1 × c14c0 × c15c2 × c13c0 × c15c4 × c11c0 × c15c7 × c8
c1 × c14c3 × c12c1 × c14c5 × c10c1 × c14c6 × c9c2 × c13c3 × c12
c2 × c13c5 × c10c2 × c13c6 × c9c3 × c12c4 × c11c3 × c12c7 × c8
c4 × c11c5 × c10c4 × c11c6 × c9c5 × c10c7 × c8c6 × c9c7 × c8

These nuggets are balanced.

We can extend this. In a non-entangled qureg, ci × cj will equal ck × cl if two conditions are met, namely

• i AND j = k AND l
• i OR j = k OR l

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.
c0 × c15c3 × c12c0 × c15c5 × c10c0 × c15c6 × c9c1 × c14c2 × c3
c1 × c14c4 × c11c1 × c14c7 × c8c2 × c13c4 × c11c2 × c13c7 × c8
c3 × c12c5 × c10c3 × c12c6 × c9c4 × c11c7 × c8c5 × c10c6 × c9

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, c2 appears it is always multiplied by c13. It is easy to contrive an example where each of c2 and c13 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) × 2n−2 where C is the combination function.

More broadly, the quantity of nuggets with a b-bit difference is C (n, b) × 2nb. This figure is O(2n) (see big O notation) in contrast to the quantity of all nuggets, which is O(4n). 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 ci × cj, analogous to table 1. Table 5 is arranged so that each amplitude appears once in each (double) row.

Table 5.
Row 0 c0 × c3c1 × c2c4 × c7c5 × c6c8 × c11c9 × c10c12 × c15c13 × c14
c16 × c19c17 × c18c20 × c23c21 × c22c24 × c27c25 × c26c28 × c31c29 × c30
Row 1 c0 × c5c1 × c4c2 × c7c3 × c6c8 × c13c9 × c12c10 × c15c11 × c14
c16 × c21c17 × c20c18 × c23c19 × c22c24 × c29c25 × c28c26 × c31c27 × c30
Row 2 c0 × c6c2 × c4c1 × c7c3 × c5c8 × c14c10 × c12c9 × c15c11 × c13
c16 × c22c18 × c20c17 × c23c19 × c21c24 × c30c26 × c28c25 × c31c27 × c29
Row 3 c0 × c9c1 × c8c2 × c11c3 × c10c4 × c13c5 × c12c6 × c15c7 × c14
c16 × c25c17 × c24c18 × c27c19 × c26c20 × c29c21 × c28c22 × c31c23 × c30
Row 4 c0 × c10c2 × c8c1 × c11c3 × c9c4 × c14c6 × c12c5 × c15c7 × c13
c16 × c26c18 × c24c17 × c27c19 × c25c20 × c30c22 × c28c21 × c31c23 × c29
Row 5 c0 × c12c4 × c8c1 × c13c5 × c9c2 × c14c6 × c10c3 × c15c7 × c11
c16 × c28c20 × c24c17 × c29c21 × c25c18 × c30c22 × c26c19 × c31c23 × c27
Row 6 c0 × c17c1 × c16c2 × c19c3 × c18c4 × c21c5 × c20c6 × c23c7 × c22
c8 × c25c9 × c24c10 × c27c11 × c26c12 × c29c13 × c28c14 × c31c15 × c30
Row 7 c0 × c18c2 × c16c1 × c19c3 × c17c4 × c22c6 × c20c5 × c23c7 × c21
c8 × c26c10 × c24c9 × c27c11 × c25c12 × c30c14 × c28c13 × c31c15 × c29
Row 8 c0 × c20c4 × c16c1 × c21c5 × c17c2 × c22c6 × c18c3 × c23c7 × c19
c8 × c28c12 × c24c9 × c29c13 × c25c10 × c30c14 × c26c11 × c31c15 × c27
Row 9 c0 × c24c8 × c16c1 × c25c9 × c17c2 × c26c10 × c18c3 × c27c11 × c19
c4 × c28c12 × c20c5 × c29c13 × c21c6 × c30c14 × c22c7 × c31c15 × c23

The minimal number of nuggets needed to detect naïve entantanglement in a qureg of n qubits is 2nn − 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 ≥ 2n ≥ 3n ≥ 4n ≥ 5
c0 × c3c1 × c2c0 × c5c1 × c4c0 × c9c1 × c8c0 × c17c1 × c16
c0 × c6c2 × c4c0 × c10c2 × c8c0 × c18c2 × c16
c1 × c7c3 × c5c1 × c11c3 × c9c1 × c19c3 × c17
c0 × c12c4 × c8c0 × c20c4 × c16
c1 × c13c5 × c9c1 × c21c5 × c17
c2 × c14c6 × c10c2 × c22c6 × c18
c3 × c15c7 × c11c3 × c23c7 × c19
c0 × c24c8 × c16
c1 × c25c9 × c17
c2 × c26c10 × c18
c3 × c27c11 × c19
c4 × c28c12 × c20
c5 × c29c13 × c21
c6 × c30c14 × c22
c7 × c31c15 × c23

Here is the method for building an unentangled qureg that motivated the nugget choice above:

• Arbitrarily choose c0, c1 and c2. They define c3.
• Arbitrarily choose c4. Now c5 through c7 are defined.
• Arbitrarily choose c8. Now c9 through c15 are defined.
• Arbitrarily choose c16. Now c17 through c31 are defined.

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.