Repository: quantumlib/OpenFermion
Pull request #540 (2019-10-11 22:42:52)

Added qubit partition functions
An implementation of the partial state tomography methods for qubits that we introduced in https://arxiv.org/pdf/1908.05628.pdf .

kevinsung: Hi @obriente , I think you missed a few of my comments. Perhaps you need to expand the "hidden conversations" to see them?
obriente: Indeed I did - sorry about that. I think I've got all of them now.

Patch:
diff --git a/examples/openfermion_tutorial.ipynb b/examples/openfermion_tutorial.ipynb
index 0f7f149..ca3fe91 100644
--- a/examples/openfermion_tutorial.ipynb
+++ b/examples/openfermion_tutorial.ipynb
@@ -1367,7 +1367,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
-   "version": "3.6.5"
+   "version": "3.7.3"
   }
  },
  "nbformat": 4,
diff --git a/src/openfermion/measurements/__init__.py b/src/openfermion/measurements/__init__.py
index 66c4b91..84a4d58 100644
--- a/src/openfermion/measurements/__init__.py
+++ b/src/openfermion/measurements/__init__.py
@@ -17,3 +17,7 @@ from ._equality_constraint_projection import (apply_constraints,
 
 from ._rdm_equality_constraints import (one_body_fermion_constraints,
                                         two_body_fermion_constraints)
+
+from ._qubit_partitioning import (binary_partition_iterator,
+                                  partition_iterator,
+                                  pauli_string_iterator)
diff --git a/src/openfermion/measurements/_qubit_partitioning.py b/src/openfermion/measurements/_qubit_partitioning.py
new file mode 100644
index 0000000..a23a070
--- /dev/null
+++ b/src/openfermion/measurements/_qubit_partitioning.py
@@ -0,0 +1,164 @@
+#   Licensed under the Apache License, Version 2.0 (the "License");
+#   you may not use this file except in compliance with the License.
+#   You may obtain a copy of the License at
+#
+#       http://www.apache.org/licenses/LICENSE-2.0
+#
+#   Unless required by applicable law or agreed to in writing, software
+#   distributed under the License is distributed on an "AS IS" BASIS,
+#   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#   See the License for the specific language governing permissions and
+#   limitations under the License.
+
+
+""" Code to generate Pauli strings for measurement of local operators"""
+from __future__ import division
+import numpy
+from itertools import chain
+try:
+    from itertools import zip_longest
+except ImportError:
+    from itertools import izip_longest as zip_longest
+
+
+def binary_partition_iterator(qubit_list, num_iterations=None):
+    """Generator for a list of 2-partitions of N qubits
+    such that all pairs of qubits are split in at least one partition,
+    This follows a variation on ArXiv:1908.0562 - instead of
+    explicitly partitioning the list based on the binary indices of
+    the qubits, we repeatedly divide the list in two and then
+    zip it back together.
+
+    Args:
+        qubit_list(list): list of qubits to be partitioned
+        num_iterations(int or None): number of iterations to perform.
+            If None, will be set to ceil(log2(len(qubit_list)))
+
+    Returns:
+        partition(iterator of tuples of lists): the required partitioning
+    """
+
+    # Some edge cases
+    if num_iterations is not None and num_iterations == 0:
+        return
+    num_qubits = len(qubit_list)
+    if num_qubits < 2:
+        raise ValueError('Need at least 2 qubits to partition')
+    if num_qubits == 2:
+        yield ([qubit_list[0]], [qubit_list[1]])
+        return
+
+    if num_iterations is None:
+        num_iterations = int(numpy.ceil(numpy.log2(num_qubits)))
+
+    # Calculate the point where we need to split the list each time.
+    half_point = int(numpy.ceil(num_qubits/2))
+
+    # Repeat the division and zip steps as many times
+    # as required.
+    for j in range(num_iterations):
+        # Divide the qubit list in two and return it
+        partition = (qubit_list[:half_point],
+                     qubit_list[half_point:])
+        yield partition
+        # Zip the partition together to remake the qubit list.
+        qubit_list = list(chain(*zip_longest(partition[0], partition[1])))
+        # If len(qubit_list) is odd, the end of the list will be 'None'
+        # which we delete.
+        if qubit_list[-1] is None:
+            del qubit_list[-1]
+        
+
+def partition_iterator(qubit_list, partition_size, num_iterations=None):
+    """Generator for a list of k-partitions of N qubits such that
+    all sets of k qubits are perfectly split in at least one
+    partition, following ArXiv:1908.05628
+
+    Args:
+        qubit_list(list): list of qubits to be partitioned
+        partition_size(int): the number of sets in the partition.
+        num_iterations(int or None): the number of iterations in the
+            outer iterator. If None, set to ceil(log2(len(qubit_list)))
+
+    Returns:
+        partition(iterator of tuples of lists): the required partitioning
+    """
+
+    # Some edge cases
+    if num_iterations == 0:
+        return
+    if partition_size == 1:
+        yield (qubit_list, )
+        return
+    elif partition_size == 2:
+        for p in binary_partition_iterator(qubit_list, num_iterations):
+            yield p
+        return
+    num_qubits = len(qubit_list)
+    if partition_size == num_qubits:
+        yield tuple([q] for q in qubit_list)
+        return
+    elif partition_size > num_qubits:
+        raise ValueError('I cant k-partition less than k qubits')
+
+    if num_iterations is None:
+        num_iterations = int(numpy.ceil(numpy.log2(num_qubits)))
+
+    # First iterate over the outer binary partition
+    outer_iterator = binary_partition_iterator(
+        qubit_list, num_iterations=num_iterations)
+    for set1, set2 in outer_iterator:
+
+        # Each new partition needs to be subdivided fewer times
+        # to prevent an additional k! factor in the scaling.
+        num_iterations -= 1
+
+        # Iterate over all possibilities of partitioning the first
+        # set into l parts and the second set into k - l parts.
+        for inner_partition_size in range(1, partition_size):
+            if inner_partition_size > len(set1) or\
+                    partition_size - inner_partition_size > len(set2):
+                continue
+
+            # subdivide the first partition
+            inner_iterator1 = partition_iterator(
+                set1, inner_partition_size, num_iterations)
+            for inner_partition1 in inner_iterator1:
+
+                # subdivide the second partition
+                inner_iterator2 = partition_iterator(
+                    set2, partition_size-inner_partition_size,
+                    num_iterations)
+                for inner_partition2 in inner_iterator2:
+                    yield inner_partition1 + inner_partition2
+
+
+def pauli_string_iterator(num_qubits, max_word_size=2):
+    """Generates a set of Pauli strings such that each word
+    of k Pauli operators lies in at least one string.
+
+    Args:
+        num_qubits(int): number of qubits in string
+        max_word_size(int): maximum required word
+
+    Returns:
+        pauli_string(iterator of strings): iterator
+            over Pauli strings
+    """
+    if max_word_size > num_qubits:
+        raise ValueError('Number of qubits is too few')
+    if max_word_size <= 0:
+        raise ValueError('Word size too small')
+
+    qubit_list = list(range(num_qubits))
+    partitions = partition_iterator(qubit_list, max_word_size)
+    pauli_string = ['I' for temp in range(num_qubits)]
+    pauli_letters = ['X', 'Y', 'Z']
+    for partition in partitions:
+        for lettering in range(3**max_word_size):
+            for p in partition:
+                letter = pauli_letters[lettering % 3]
+                for qubit in p:
+                    pauli_string[qubit] = letter
+                lettering = lettering // 3
+            yield tuple(pauli_string)


Test patch:
diff --git a/src/openfermion/measurements/_qubit_partitioning_test.py b/src/openfermion/measurements/_qubit_partitioning_test.py
new file mode 100644
index 0000000..f6b471a
--- /dev/null
+++ b/src/openfermion/measurements/_qubit_partitioning_test.py
@@ -0,0 +1,191 @@
+#   Licensed under the Apache License, Version 2.0 (the "License");
+#   you may not use this file except in compliance with the License.
+#   You may obtain a copy of the License at
+#
+#       http://www.apache.org/licenses/LICENSE-2.0
+#
+#   Unless required by applicable law or agreed to in writing, software
+#   distributed under the License is distributed on an "AS IS" BASIS,
+#   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#   See the License for the specific language governing permissions and
+#   limitations under the License.
+
+
+"""Tests for _qubit_partitioning.py"""
+import unittest
+from ._qubit_partitioning import (
+    binary_partition_iterator, partition_iterator,
+    pauli_string_iterator)
+
+
+class BinaryPartitionIteratorTest(unittest.TestCase):
+
+    def test_num_partitions(self):
+        qubit_list = range(6)
+        bpi = binary_partition_iterator(qubit_list)
+        count = 0
+        for p1, p2 in bpi:
+            count += 1
+        self.assertEqual(count, 3)
+
+    def test_partition_size(self):
+        qubit_list = range(6)
+        bpi = binary_partition_iterator(qubit_list)
+        for p1, p2 in bpi:
+            self.assertEqual(len(p1), 3)
+            self.assertEqual(len(p2), 3)
+
+    def test_partition_size_odd(self):
+        qubit_list = range(7)
+        bpi = binary_partition_iterator(qubit_list)
+        for p1, p2 in bpi:
+            self.assertEqual(len(p1), 4)
+            self.assertEqual(len(p2), 3)
+
+    def test_partitioning(self):
+        qubit_list = list(range(6))
+        for i in range(6):
+            for j in range(i+1, 6):
+                print(i, j)
+                flag = False
+                bpi = binary_partition_iterator(qubit_list)
+                for partition in bpi:
+                    print(type(partition))
+                    self.assertTrue(type(partition) is tuple)
+                    p1, p2 = partition
+                    print(p1, p2)
+                    if (i in p1 and j in p2) or (j in p1 and i in p2):
+                        flag = True
+                self.assertTrue(flag)
+
+    def test_partitioning_odd(self):
+        qubit_list = list(range(7))
+        for i in range(7):
+            for j in range(i+1, 7):
+                print(i, j)
+                flag = False
+                bpi = binary_partition_iterator(qubit_list)
+                for p1, p2 in bpi:
+                    print(p1, p2)
+                    if (i in p1 and j in p2) or (j in p1 and i in p2):
+                        flag = True
+                self.assertTrue(flag)
+
+    def test_exception(self):
+        with self.assertRaises(ValueError):
+            bpi = binary_partition_iterator([])
+            next(bpi)
+
+    def test_partition_of_two(self):
+        bpi = binary_partition_iterator([0, 1])
+        count = 0
+        for p1, p2 in bpi:
+            count += 1
+            self.assertEqual(p1[0], 0)
+            self.assertEqual(p2[0], 1)
+        self.assertEqual(count, 1)
+
+    def test_zero_counting(self):
+        bpi = binary_partition_iterator([0, 1], 0)
+        with self.assertRaises(StopIteration):
+            next(bpi)
+
+
+class PartitionIteratorTest(unittest.TestCase):
+
+    def test_unary_case(self):
+        qubit_list = list(range(6))
+        bpi = partition_iterator(qubit_list, 1)
+        for p1, in bpi:
+            self.assertEqual(p1, qubit_list)
+
+    def test_binary_case(self):
+        qubit_list = list(range(6))
+        for i in range(6):
+            for j in range(i+1, 6):
+                print(i, j)
+                flag = False
+                bpi = partition_iterator(qubit_list, 2)
+                for p1, p2 in bpi:
+                    print(p1, p2)
+                    if (i in p1 and j in p2) or (j in p1 and i in p2):
+                        flag = True
+                self.assertTrue(flag)
+
+    def test_exception(self):
+        with self.assertRaises(ValueError):
+            pi = partition_iterator([1, 2], 3)
+            next(pi)
+
+    def test_threepartition_three(self):
+        bpi = partition_iterator([1, 2, 3], 3)
+        count = 0
+        for partition in bpi:
+            print(type(partition))
+            self.assertTrue(type(partition) is tuple)
+            p1, p2, p3 = partition
+            print(p1, p2, p3)
+            self.assertEqual(len(p1), 1)
+            self.assertEqual(p1[0], 1)
+            self.assertEqual(len(p2), 1)
+            self.assertEqual(p2[0], 2)
+            self.assertEqual(len(p3), 1)
+            self.assertEqual(p3[0], 3)
+            count += 1
+        self.assertEqual(count, 1)
+
+    def test_partition_three(self):
+        for num_qubits in range(1, 16):
+            qubit_list = list(range(num_qubits))
+            for i in range(num_qubits):
+                for j in range(i+1, num_qubits):
+                    for k in range(j+1, num_qubits):
+                        print('Testing {}, {}, {}'.format(i, j, k))
+                        pi = partition_iterator(qubit_list, 3)
+                        count = 0
+                        for p1, p2, p3 in pi:
+                            self.assertEqual(len(p1)+len(p2)+len(p3),
+                                             len(qubit_list))
+                            self.assertEqual(set(p1 + p2 + p3),
+                                             set(qubit_list))
+                            print('Partition obtained: ', p1, p2, p3)
+                            if max(sum(1 for x in p if x in [i, j, k])
+                                    for p in [p1, p2, p3]) == 1:
+                                count += 1
+                        print('count = {}'.format(count))
+                        self.assertTrue(count > 0)
+                        print()
+
+
+class PauliStringIteratorTest(unittest.TestCase):
+
+    def test_eightpartition_three(self):
+        for i1 in range(8):
+            for i2 in range(i1+1, 8):
+                for i3 in range(i2+1, 8):
+                    for l1 in ['X', 'Y', 'Z']:
+                        for l2 in ['X', 'Y', 'Z']:
+                            for l3 in ['X', 'Y', 'Z']:
+                                psg = pauli_string_iterator(8, 3)
+                                count = 0
+                                for pauli_string in psg:
+                                    if (pauli_string[i1] == l1 and
+                                            pauli_string[i2] == l2 and
+                                            pauli_string[i3] == l3):
+                                        count += 1
+                                self.assertTrue(count > 0)
+
+    def test_exceptions(self):
+        with self.assertRaises(ValueError):
+            psi = pauli_string_iterator(1, 2)
+            next(psi)
+        with self.assertRaises(ValueError):
+            psi = pauli_string_iterator(3, -1)
+            next(psi)
+
+    def test_small_run_cases(self):
+        for num_qubits in range(4, 20):
+            for word_length in range(2, min(num_qubits, 5)):
+                psi = pauli_string_iterator(num_qubits, word_length)
+                for _ in psi:
+                    pass