9676490291

Committed 26 Jun 2024 08:46AM UTC coverage: 87.215% (+0.02%) from 87.199%

Build # 9676490291

Build Type

Pull #12665

github

Committed by

mergify[bot]

Commit Message

Fix some bugs in loading Solovay Kitaev decompositions (#12579)

* fix store & load

- fix access via .item()
- fix storing of global phase
- fix storing ofgate sequence labels

* undangle a dangling print

* fix import order

* Update releasenotes/notes/fix-sk-load-from-file-02c6eabbbd7fcda3.yaml

Co-authored-by: Elena Peña Tapia <57907331+ElePT@users.noreply.github.com>

---------

Co-authored-by: Elena Peña Tapia <57907331+ElePT@users.noreply.github.com>
(cherry picked from commit 6974b4500)

Pull Request Pull Request #12665: Fix some bugs in loading Solovay Kitaev decompositions (backport #12579)

Run Details

9 of 10 new or added lines in 2 files covered. (90.0%)

4 existing lines in 2 files now uncovered.

74528 of 85453 relevant lines covered (87.22%)

101769.48 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.74

/qiskit/synthesis/discrete_basis/solovay_kitaev.py

# This code is part of Qiskit.
#
# (C) Copyright IBM 2017, 2020.
#
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
#
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.

"""Synthesize a single qubit gate to a discrete basis set."""

from __future__ import annotations

import numpy as np

from .gate_sequence import GateSequence
from .commutator_decompose import commutator_decompose
from .generate_basis_approximations import generate_basic_approximations, _1q_gates, _1q_inverses


class SolovayKitaevDecomposition:
    """The Solovay Kitaev discrete decomposition algorithm.

    This class is called recursively by the transpiler pass, which is why it is separeted.
    See :class:`qiskit.transpiler.passes.SolovayKitaev` for more information.
    """

    def __init__(
        self, basic_approximations: str | dict[str, np.ndarray] | list[GateSequence] | None = None
    ) -> None:
        """
        Args:
            basic_approximations: A specification of the basic SU(2) approximations in terms
                of discrete gates. At each iteration this algorithm, the remaining error is
                approximated with the closest sequence of gates in this set.
                If a ``str``, this specifies a ``.npy`` filename from which to load the
                approximation. If a ``dict``, then this contains
                ``{gates: effective_SO3_matrix}`` pairs,
                e.g. ``{"h t": np.array([[0, 0.7071, -0.7071], [0, -0.7071, -0.7071], [-1, 0, 0]]}``.
                If a list, this contains the same information as the dict, but already converted to
                :class:`.GateSequence` objects, which contain the SO(3) matrix and gates.
        """
        if basic_approximations is None:
            # generate a default basic approximation
            basic_approximations = generate_basic_approximations(
                basis_gates=["h", "t", "tdg"], depth=10
            )

        self.basic_approximations = self.load_basic_approximations(basic_approximations)

    @staticmethod
    def load_basic_approximations(data: list | str | dict) -> list[GateSequence]:
        """Load basic approximations.

        Args:
            data: If a string, specifies the path to the file from where to load the data.
                If a dictionary, directly specifies the decompositions as ``{gates: matrix}``
                or ``{gates: (matrix, global_phase)}``. There, ``gates`` are the names of the gates
                producing the SO(3) matrix ``matrix``, e.g.
                ``{"h t": np.array([[0, 0.7071, -0.7071], [0, -0.7071, -0.7071], [-1, 0, 0]]}``
                and the ``global_phase`` can be given to account for a global phase difference
                between the U(2) matrix of the quantum gates and the stored SO(3) matrix.
                If not given, the ``global_phase`` will be assumed to be 0.

        Returns:
            A list of basic approximations as type ``GateSequence``.

        Raises:
            ValueError: If the number of gate combinations and associated matrices does not match.
        """
        # is already a list of GateSequences
        if isinstance(data, list):
            return data

        # if a file, load the dictionary
        if isinstance(data, str):
            data = np.load(data, allow_pickle=True).item()

        sequences = []
        for gatestring, matrix_and_phase in data.items():
            if isinstance(matrix_and_phase, tuple):
                matrix, global_phase = matrix_and_phase
            else:
                matrix, global_phase = matrix_and_phase, 0

            sequence = GateSequence()
            sequence.gates = [_1q_gates[element] for element in gatestring.split()]
            sequence.labels = [gate.name for gate in sequence.gates]
            sequence.product = np.asarray(matrix)
            sequence.global_phase = global_phase
            sequences.append(sequence)

        return sequences

    def run(
        self,
        gate_matrix: np.ndarray,
        recursion_degree: int,
        return_dag: bool = False,
        check_input: bool = True,
    ) -> "QuantumCircuit" | "DAGCircuit":
        r"""Run the algorithm.

        Args:
            gate_matrix: The 2x2 matrix representing the gate. This matrix has to be SU(2)
                up to global phase.
            recursion_degree: The recursion degree, called :math:`n` in the paper.
            return_dag: If ``True`` return a :class:`.DAGCircuit`, else a :class:`.QuantumCircuit`.
            check_input: If ``True`` check that the input matrix is valid for the decomposition.

        Returns:
            A one-qubit circuit approximating the ``gate_matrix`` in the specified discrete basis.
        """
        # make input matrix SU(2) and get the according global phase
        z = 1 / np.sqrt(np.linalg.det(gate_matrix))
        gate_matrix_su2 = GateSequence.from_matrix(z * gate_matrix)
        global_phase = np.arctan2(np.imag(z), np.real(z))

        # get the decompositon as GateSequence type
        decomposition = self._recurse(gate_matrix_su2, recursion_degree, check_input=check_input)

        # simplify
        _remove_identities(decomposition)
        _remove_inverse_follows_gate(decomposition)

        # convert to a circuit and attach the right phases
        if return_dag:
            out = decomposition.to_dag()
        else:
            out = decomposition.to_circuit()

        out.global_phase = decomposition.global_phase - global_phase

        return out

    def _recurse(self, sequence: GateSequence, n: int, check_input: bool = True) -> GateSequence:
        """Performs ``n`` iterations of the Solovay-Kitaev algorithm on ``sequence``.

        Args:
            sequence: ``GateSequence`` to which the Solovay-Kitaev algorithm is applied.
            n: The number of iterations that the algorithm needs to run.
            check_input: If ``True`` check that the input matrix represented by ``GateSequence``
                is valid for the decomposition.

        Returns:
            GateSequence that approximates ``sequence``.

        Raises:
            ValueError: If the matrix in ``GateSequence`` does not represent an SO(3)-matrix.
        """
        if sequence.product.shape != (3, 3):
            raise ValueError("Shape of U must be (3, 3) but is", sequence.shape)

        if n == 0:
            return self.find_basic_approximation(sequence)

        u_n1 = self._recurse(sequence, n - 1, check_input=check_input)

        v_n, w_n = commutator_decompose(
            sequence.dot(u_n1.adjoint()).product, check_input=check_input
        )

        v_n1 = self._recurse(v_n, n - 1, check_input=check_input)
        w_n1 = self._recurse(w_n, n - 1, check_input=check_input)
        return v_n1.dot(w_n1).dot(v_n1.adjoint()).dot(w_n1.adjoint()).dot(u_n1)

    def find_basic_approximation(self, sequence: GateSequence) -> GateSequence:
        """Find ``GateSequence`` in ``self._basic_approximations`` that approximates ``sequence``.

        Args:
            sequence: ``GateSequence`` to find the approximation to.

        Returns:
            ``GateSequence`` in ``self._basic_approximations`` that approximates ``sequence``.
        """
        # TODO explore using a k-d tree here

        def key(x):
            return np.linalg.norm(np.subtract(x.product, sequence.product))

        best = min(self.basic_approximations, key=key)
        return best


def _remove_inverse_follows_gate(sequence):
    index = 0
    while index < len(sequence.gates) - 1:
        curr_gate = sequence.gates[index]
        next_gate = sequence.gates[index + 1]
        if curr_gate.name in _1q_inverses.keys():
            remove = _1q_inverses[curr_gate.name] == next_gate.name
        else:
            remove = curr_gate.inverse() == next_gate

        if remove:
            # remove gates at index and index + 1
            sequence.remove_cancelling_pair([index, index + 1])
            # take a step back to see if we have uncovered a new pair, e.g.
            # [h, s, sdg, h] at index = 1 removes s, sdg but if we continue at index 1
            # we miss the uncovered [h, h] pair at indices 0 and 1
            if index > 0:
                index -= 1
        else:
            # next index
            index += 1


def _remove_identities(sequence):
    index = 0
    while index < len(sequence.gates):
        if sequence.gates[index].name == "id":
            sequence.gates.pop(index)
        else:
            index += 1

1	# This code is part of Qiskit.
2	#
3	# (C) Copyright IBM 2017, 2020.
4	#
5	# This code is licensed under the Apache License, Version 2.0. You may
6	# obtain a copy of this license in the LICENSE.txt file in the root directory
7	# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
8	#
9	# Any modifications or derivative works of this code must retain this
10	# copyright notice, and modified files need to carry a notice indicating
11	# that they have been altered from the originals.
12
13	"""Synthesize a single qubit gate to a discrete basis set."""	1✔
14
15	from __future__ import annotations	1✔
16
17	import numpy as np	1✔
18
19	from .gate_sequence import GateSequence	1✔
20	from .commutator_decompose import commutator_decompose	1✔
21	from .generate_basis_approximations import generate_basic_approximations, _1q_gates, _1q_inverses	1✔
22
23
24	class SolovayKitaevDecomposition:	1✔
25	"""The Solovay Kitaev discrete decomposition algorithm.	1✔
26
27	This class is called recursively by the transpiler pass, which is why it is separeted.
28	See :class:`qiskit.transpiler.passes.SolovayKitaev` for more information.
29	"""
30
31	def __init__(	1✔
32	self, basic_approximations: str \| dict[str, np.ndarray] \| list[GateSequence] \| None = None
33	) -> None:
34	"""
35	Args:
36	basic_approximations: A specification of the basic SU(2) approximations in terms
37	of discrete gates. At each iteration this algorithm, the remaining error is
38	approximated with the closest sequence of gates in this set.
39	If a ``str``, this specifies a ``.npy`` filename from which to load the
40	approximation. If a ``dict``, then this contains
41	``{gates: effective_SO3_matrix}`` pairs,
42	e.g. ``{"h t": np.array([[0, 0.7071, -0.7071], [0, -0.7071, -0.7071], [-1, 0, 0]]}``.
43	If a list, this contains the same information as the dict, but already converted to
44	:class:`.GateSequence` objects, which contain the SO(3) matrix and gates.
45	"""
46	if basic_approximations is None:	1✔
47	# generate a default basic approximation
48	basic_approximations = generate_basic_approximations(	1✔
49	basis_gates=["h", "t", "tdg"], depth=10
50	)
51
52	self.basic_approximations = self.load_basic_approximations(basic_approximations)	1✔
53
54	@staticmethod	1✔
55	def load_basic_approximations(data: list \| str \| dict) -> list[GateSequence]:	1✔
56	"""Load basic approximations.
57
58	Args:
59	data: If a string, specifies the path to the file from where to load the data.
60	If a dictionary, directly specifies the decompositions as ``{gates: matrix}``
61	or ``{gates: (matrix, global_phase)}``. There, ``gates`` are the names of the gates
62	producing the SO(3) matrix ``matrix``, e.g.
63	``{"h t": np.array([[0, 0.7071, -0.7071], [0, -0.7071, -0.7071], [-1, 0, 0]]}``
64	and the ``global_phase`` can be given to account for a global phase difference
65	between the U(2) matrix of the quantum gates and the stored SO(3) matrix.
66	If not given, the ``global_phase`` will be assumed to be 0.
67
68	Returns:
69	A list of basic approximations as type ``GateSequence``.
70
71	Raises:
72	ValueError: If the number of gate combinations and associated matrices does not match.
73	"""
74	# is already a list of GateSequences
75	if isinstance(data, list):	1✔
76	return data	1✔
77
78	# if a file, load the dictionary
79	if isinstance(data, str):	1✔
80	data = np.load(data, allow_pickle=True).item()	1✔
81
82	sequences = []	1✔
83	for gatestring, matrix_and_phase in data.items():	1✔
84	if isinstance(matrix_and_phase, tuple):	1✔
85	matrix, global_phase = matrix_and_phase	1✔
86	else:
NEW 87	matrix, global_phase = matrix_and_phase, 0	×
88
89	sequence = GateSequence()	1✔
90	sequence.gates = [_1q_gates[element] for element in gatestring.split()]	1✔
91	sequence.labels = [gate.name for gate in sequence.gates]	1✔
92	sequence.product = np.asarray(matrix)	1✔
93	sequence.global_phase = global_phase	1✔
94	sequences.append(sequence)	1✔
95
96	return sequences	1✔
97
98	def run(	1✔
99	self,
100	gate_matrix: np.ndarray,
101	recursion_degree: int,
102	return_dag: bool = False,
103	check_input: bool = True,
104	) -> "QuantumCircuit" \| "DAGCircuit":
105	r"""Run the algorithm.
106
107	Args:
108	gate_matrix: The 2x2 matrix representing the gate. This matrix has to be SU(2)
109	up to global phase.
110	recursion_degree: The recursion degree, called :math:`n` in the paper.
111	return_dag: If ``True`` return a :class:`.DAGCircuit`, else a :class:`.QuantumCircuit`.
112	check_input: If ``True`` check that the input matrix is valid for the decomposition.
113
114	Returns:
115	A one-qubit circuit approximating the ``gate_matrix`` in the specified discrete basis.
116	"""
117	# make input matrix SU(2) and get the according global phase
118	z = 1 / np.sqrt(np.linalg.det(gate_matrix))	1✔
119	gate_matrix_su2 = GateSequence.from_matrix(z * gate_matrix)	1✔
120	global_phase = np.arctan2(np.imag(z), np.real(z))	1✔
121
122	# get the decompositon as GateSequence type
123	decomposition = self._recurse(gate_matrix_su2, recursion_degree, check_input=check_input)	1✔
124
125	# simplify
126	_remove_identities(decomposition)	1✔
127	_remove_inverse_follows_gate(decomposition)	1✔
128
129	# convert to a circuit and attach the right phases
130	if return_dag:	1✔
131	out = decomposition.to_dag()	1✔
132	else:
133	out = decomposition.to_circuit()	1✔
134
135	out.global_phase = decomposition.global_phase - global_phase	1✔
136
137	return out	1✔
138
139	def _recurse(self, sequence: GateSequence, n: int, check_input: bool = True) -> GateSequence:	1✔
140	"""Performs ``n`` iterations of the Solovay-Kitaev algorithm on ``sequence``.
141
142	Args:
143	sequence: ``GateSequence`` to which the Solovay-Kitaev algorithm is applied.
144	n: The number of iterations that the algorithm needs to run.
145	check_input: If ``True`` check that the input matrix represented by ``GateSequence``
146	is valid for the decomposition.
147
148	Returns:
149	GateSequence that approximates ``sequence``.
150
151	Raises:
152	ValueError: If the matrix in ``GateSequence`` does not represent an SO(3)-matrix.
153	"""
154	if sequence.product.shape != (3, 3):	1✔
155	raise ValueError("Shape of U must be (3, 3) but is", sequence.shape)	×
156
157	if n == 0:	1✔
158	return self.find_basic_approximation(sequence)	1✔
159
160	u_n1 = self._recurse(sequence, n - 1, check_input=check_input)	1✔
161
162	v_n, w_n = commutator_decompose(	1✔
163	sequence.dot(u_n1.adjoint()).product, check_input=check_input
164	)
165
166	v_n1 = self._recurse(v_n, n - 1, check_input=check_input)	1✔
167	w_n1 = self._recurse(w_n, n - 1, check_input=check_input)	1✔
168	return v_n1.dot(w_n1).dot(v_n1.adjoint()).dot(w_n1.adjoint()).dot(u_n1)	1✔
169
170	def find_basic_approximation(self, sequence: GateSequence) -> GateSequence:	1✔
171	"""Find ``GateSequence`` in ``self._basic_approximations`` that approximates ``sequence``.
172
173	Args:
174	sequence: ``GateSequence`` to find the approximation to.
175
176	Returns:
177	``GateSequence`` in ``self._basic_approximations`` that approximates ``sequence``.
178	"""
179	# TODO explore using a k-d tree here
180
181	def key(x):	1✔
182	return np.linalg.norm(np.subtract(x.product, sequence.product))	1✔
183
184	best = min(self.basic_approximations, key=key)	1✔
185	return best	1✔
186
187
188	def _remove_inverse_follows_gate(sequence):	1✔
189	index = 0	1✔
190	while index < len(sequence.gates) - 1:	1✔
191	curr_gate = sequence.gates[index]	1✔
192	next_gate = sequence.gates[index + 1]	1✔
193	if curr_gate.name in _1q_inverses.keys():	1✔
194	remove = _1q_inverses[curr_gate.name] == next_gate.name	1✔
195	else:
196	remove = curr_gate.inverse() == next_gate	×
197
198	if remove:	1✔
199	# remove gates at index and index + 1
200	sequence.remove_cancelling_pair([index, index + 1])	1✔
201	# take a step back to see if we have uncovered a new pair, e.g.
202	# [h, s, sdg, h] at index = 1 removes s, sdg but if we continue at index 1
203	# we miss the uncovered [h, h] pair at indices 0 and 1
204	if index > 0:	1✔
205	index -= 1	1✔
206	else:
207	# next index
208	index += 1	1✔
209
210
211	def _remove_identities(sequence):	1✔
212	index = 0	1✔
213	while index < len(sequence.gates):	1✔
214	if sequence.gates[index].name == "id":	1✔
215	sequence.gates.pop(index)	×
216	else:
217	index += 1	1✔

Qiskit / qiskit / 9676490291

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous