1# Copyright 2019 The Cirq Developers
2#
3# Licensed under the Apache License, Version 2.0 (the "License");
4# you may not use this file except in compliance with the License.
5# You may obtain a copy of the License at
6#
7#      http://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS,
11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12# See the License for the specific language governing permissions and
13# limitations under the License.
14import abc
15from typing import (
16    Callable,
17    Optional,
18    List,
19    NamedTuple,
20    Any,
21    Iterable,
22    Sequence,
23    TYPE_CHECKING,
24    Union,
25    Dict,
26    Tuple,
27)
28
29from cirq import ops, value, devices
30
31if TYPE_CHECKING:
32    import cirq
33
34
35class Cell(metaclass=abc.ABCMeta):
36    """A gate, operation, display, operation modifier, etc from Quirk.
37
38    Represents something that can go into a column in Quirk, and supports the
39    operations ultimately necessary to transform a grid of these cells into a
40    `cirq.Circuit`.
41    """
42
43    @classmethod
44    def _replace_qubit(cls, old_qubit: 'cirq.Qid', qubits: List['cirq.Qid']) -> 'cirq.Qid':
45        if not isinstance(old_qubit, devices.LineQubit):
46            raise ValueError(f'Can only map from line qubits, but got {old_qubit!r}.')
47        if not 0 <= old_qubit.x < len(qubits):
48            raise ValueError(f'Line qubit index ({old_qubit.x}) not in range({len(qubits)})')
49        return qubits[old_qubit.x]
50
51    @classmethod
52    def _replace_qubits(
53        cls, old_qubits: Iterable['cirq.Qid'], qubits: List['cirq.Qid']
54    ) -> Tuple['cirq.Qid', ...]:
55        return tuple(Cell._replace_qubit(e, qubits) for e in old_qubits)
56
57    @abc.abstractmethod
58    def with_line_qubits_mapped_to(self, qubits: List['cirq.Qid']) -> 'Cell':
59        """Returns the same cell, but targeting different qubits.
60
61        It is assumed that the cell is currently targeting `LineQubit`
62        instances, where the x coordinate indicates the qubit to take from the
63        list.
64
65        Args:
66            qubits: The new qubits. The qubit at offset `x` will replace
67                `cirq.LineQubit(x)`.
68
69        Returns:
70            The same cell, but with new qubits.
71        """
72
73    @abc.abstractmethod
74    def gate_count(self) -> int:
75        """Cheaply determines an upper bound on the resulting circuit size.
76
77        The upper bound may be larger than the actual count. For example, a
78        small circuit may nevertheless have involved a huge amount of rewriting
79        work to create. In such cases the `gate_count` is permitted to be large
80        to indicate the danger, despite the output being small.
81
82        This method exists in order to defend against billion laugh type
83        attacks. It is important that counting is fast and efficient even in
84        extremely adversarial conditions.
85        """
86
87    def with_input(self, letter: str, register: Union[Sequence['cirq.Qid'], int]) -> 'Cell':
88        """The same cell, but linked to an explicit input register or constant.
89
90        If the cell doesn't need the input, it is returned unchanged.
91
92        Args:
93            letter: The input variable name ('a', 'b', or 'r').
94            register: The list of qubits to use as the input, or else a
95                classical constant to use as the input.
96
97        Returns:
98            The same cell, but with the specified input made explicit.
99        """
100        return self
101
102    def controlled_by(self, qubit: 'cirq.Qid') -> 'Cell':
103        """The same cell, but with an explicit control on its main operations.
104
105        Cells with effects that do not need to be controlled are permitted to
106        return themselves unmodified.
107
108        Args:
109            qubit: The control qubit.
110
111        Returns:
112            A modified cell with an additional control.
113        """
114        return self
115
116    def operations(self) -> 'cirq.OP_TREE':
117        """Returns operations that implement the cell's main action.
118
119        Returns:
120            A `cirq.OP_TREE` of operations implementing the cell.
121
122        Raises:
123            ValueError:
124                The cell is not ready for conversion into operations, e.g. it
125                may still have unspecified inputs.
126        """
127        return ()
128
129    def basis_change(self) -> 'cirq.OP_TREE':
130        """Operations to conjugate a column with.
131
132        The main distinctions between operations performed during the body of a
133        column and operations performed during the basis change are:
134
135        1. Basis change operations are not affected by operation modifiers in
136            the column. For example, adding a control into the same column will
137            not affect the basis change.
138        2. Basis change operations happen twice, once when starting a column and
139            a second time (but inverted) when ending a column.
140
141        Returns:
142            A `cirq.OP_TREE` of basis change operations.
143        """
144        return ()
145
146    def modify_column(self, column: List[Optional['Cell']]) -> None:
147        """Applies this cell's modification to its column.
148
149        For example, a control cell will add a control qubit to other operations
150        in the column.
151
152        Args:
153            column: A mutable list of cells in the column, including empty
154                cells (with value `None`). This method is permitted to change
155                the items in the list, but must not change the length of the
156                list.
157
158        Returns:
159            Nothing. The `column` argument is mutated in place.
160        """
161
162    def persistent_modifiers(self) -> Dict[str, Callable[['Cell'], 'Cell']]:
163        """Overridable modifications to apply to the rest of the circuit.
164
165        Persistent modifiers apply to all cells in the same column and also to
166        all cells in future columns (until a column overrides the modifier with
167        another one using the same key).
168
169        Returns:
170            A dictionary of keyed modifications. Each modifier lasts until a
171            later cell specifies a new modifier with the same key.
172        """
173        return {}
174
175
176@value.value_equality
177class ExplicitOperationsCell(Cell):
178    """A quirk cell with known body operations and basis change operations."""
179
180    def __init__(
181        self, operations: Iterable[ops.Operation], basis_change: Iterable[ops.Operation] = ()
182    ):
183        self._operations = tuple(operations)
184        self._basis_change = tuple(basis_change)
185
186    def gate_count(self) -> int:
187        return len(self._operations) + 2 * len(self._basis_change)
188
189    def with_line_qubits_mapped_to(self, qubits: List['cirq.Qid']) -> 'Cell':
190        return ExplicitOperationsCell(
191            operations=tuple(
192                op.with_qubits(*Cell._replace_qubits(op.qubits, qubits)) for op in self._operations
193            ),
194            basis_change=tuple(
195                op.with_qubits(*Cell._replace_qubits(op.qubits, qubits))
196                for op in self._basis_change
197            ),
198        )
199
200    def _value_equality_values_(self):
201        return self._operations, self._basis_change
202
203    def basis_change(self) -> 'cirq.OP_TREE':
204        return self._basis_change
205
206    def operations(self) -> 'cirq.OP_TREE':
207        return self._operations
208
209    def controlled_by(self, qubit: 'cirq.Qid') -> 'ExplicitOperationsCell':
210        return ExplicitOperationsCell(
211            [op.controlled_by(qubit) for op in self._operations], self._basis_change
212        )
213
214
215CELL_SIZES = range(1, 17)
216
217CellMakerArgs = NamedTuple(
218    'CellMakerArgs',
219    [
220        ('qubits', Sequence['cirq.Qid']),
221        ('value', Any),
222        ('row', int),
223        ('col', int),
224    ],
225)
226
227CellMaker = NamedTuple(
228    'CellMaker',
229    [
230        ('identifier', str),
231        ('size', int),
232        ('maker', Callable[[CellMakerArgs], Union[None, 'Cell', 'cirq.Operation']]),
233    ],
234)
235CellMaker.__doc__ = """Turns Quirk identifiers into Cirq operations.
236
237Attributes:
238    identifier: A string that identifies the cell type, such as "X" or "QFT3".
239    size: The height of the operation. The number of qubits it covers.
240    maker: A function that takes a `cirq.interop.quirk.cells.CellMakerArgs` and
241        returns either a `cirq.Operation` or a `cirq.interop.quirk.cells.Cell`.
242        Returning a cell is more flexible, because cells can modify other cells
243        in the same column before producing operations, whereas returning an
244        operation is simple.
245"""
246