This appendix explains how to systematically enumerate pairs of computational-basis outcomes that must be processed together when applying a single-qubit gate in an n-qubit system. The key idea is that paired outcomes differ only at the target qubit position t, so their indices in decimal form are separated by a fixed “distance” of 2^t. Two practical Python strategies are presented for generating these pairs in a deterministic and duplication-free manner.
The first strategy iterates over all outcomes from 0 to 2^n − 1 and uses a bit test to recognize the “0-side” of each pair at the target position. For any index k0 whose bit t is 0, its partner is k1 = k0 + 2^t. This produces each pair exactly once and avoids string manipulation by working directly with bitwise operations. For example, with n = 3 and t = 0, the method yields the pairs (0, 1), (2, 3), (4, 5), and (6, 7), each separated by the distance 2^t.
The second strategy constructs pairs by viewing each outcome as a concatenation of a prefix (n − t − 1 bits), the target bit, and a suffix (t bits). By iterating over all prefixes and suffixes, the “0-side” index is computed as k0 = prefix * (2 * 2^t) + suffix, and the partner is k1 = k0 + 2^t. In the example n = 4 and t = 1, this generates pairs such as (0, 2), (1, 3), (4, 6), …, (13, 15), each differing only at position t. Both approaches produce the same set of pairs; one emphasizes direct bit checks, while the other mirrors the binary structure via prefix/suffix enumeration.
Figure C.1 The pairs of outcomes for applying a single-qubit gate to a three-qubit system with target qubit in position 0.
FAQ
What is an “outcome pair” and why do we pair outcomes when applying a single-qubit gate?When a single-qubit gate acts on target qubit t in an n-qubit state, amplitudes of computational basis states come in pairs that differ only at bit t. Pairing these indices lets us update both amplitudes together using the 2x2 gate matrix, ensuring correctness and efficiency.How does the traverse-and-check method (pair_generator_check_digit) select pairs?It iterates k0 from 0 to 2^n - 1 and checks whether the target bit t is 0 using is_bit_set(k0, t). When it is 0, it defines the partner as k1 = k0 + 2^t (the distance between paired outcomes) and yields (k0, k1). This guarantees each pair is produced exactly once.What does is_bit_set(m, k) verify in the code?It returns whether bit k of integer m is 1. Implementation: (m & (1 << k)) != 0. If it’s False, the bit is 0, which identifies the “0-side” of a pair at position k.Why is the “distance” between paired outcomes equal to 2^t?Flipping bit t changes the number by exactly 2^t in decimal because bit t contributes 2^t to the value. Therefore, the partner of k0 is k1 = k0 + 2^t when k0 has bit t = 0.Can you show the pairs for n = 3 and target t = 0 using the traverse-and-check method?The generated pairs are: (0, 1), (2, 3), (4, 5), (6, 7). In binary, these differ only in bit position 0 (least significant bit).What is the idea behind the prefix–target–suffix concatenation method?Split a basis index’s binary string into prefix (bits above t), the target bit t, and suffix (bits below t). Enumerate all prefixes of length n - t - 1 and all suffixes of length t. For each (prefix, suffix), form the “0-side” with target=0 and the “1-side” with target=1; these two form a pair.How are k0 and k1 computed in the concatenation method?Let suffix_count = 2^t and prefix_count = 2^(n - t - 1). For each prefix p in [0, prefix_count) and suffix s in [0, suffix_count), compute k0 = p * (suffix_count * 2) + s. Then k1 = k0 + 2^t. This mirrors placing prefix bits above t, 0 at t, and suffix bits below t in decimal form.What pairs are generated for n = 4 and t = 1 using concatenation?The pairs are: (0, 2), (1, 3), (4, 6), (5, 7), (8, 10), (9, 11), (12, 14), (13, 15). Each pair’s elements differ by 2^1 = 2 and only in bit position 1.How do these two methods compare in complexity and usage?Both generate all 2^(n-1) pairs with overall O(2^n) time and O(1) extra space when implemented as generators. Traverse-and-check is simpler and scans all indices; concatenation structures iteration by prefix and suffix, which can be convenient for cache locality or nested-loop integration.What edge cases and pitfalls should I watch for?- Ensure 0 ≤ t ≤ n - 1 and n ≥ 1.
- Bit numbering assumes position 0 is the least significant bit; be consistent throughout your code.
- In traverse-and-check, only emit pairs when bit t is 0 to avoid duplicates.
- For large n, prefer generator-based iteration to keep memory usage low.
- Validate with small n and t to confirm ordering and pair correctness.
pro $24.99 per month
access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
Building Quantum Software with Python ebook for free
