Source code for mimiqcircuits.operations.decompositions.control

#
# Copyright © 2022-2024 University of Strasbourg. All Rights Reserved.
# Copyright © 2023-2025 QPerfect. All Rights Reserved.
#
# 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.
#

# References
# [1] Barenco, A. et al. Elementary gates for quantum computation. Phys. Rev. A 52, 3457–3467 (1995).
#



[docs] def control_decompose(circ, operation, controls, target): """Push ``operation`` on ``target`` controlled by ``controls`` to ``circ``. With zero or one control the gate is pushed directly; with more, it is decomposed recursively into singly-controlled gates and multi-controlled X gates, following Barenco et al. (1995). Args: circ: The circuit to push to. operation: A single-qubit gate. controls: The control qubits. target: The target qubit. Returns: The circuit ``circ``. """ from mimiqcircuits.operations.control import Control if len(controls) == 0: circ.push(operation, target) elif len(controls) == 1: circ.push(Control(1, operation), controls[0], target) else: control_recursive_decompose(circ, operation, controls, target) return circ
[docs] def cx_decompose(circ, controls, target, ancillas): """Push an X gate on ``target`` controlled by ``controls`` to ``circ``. Uses the free qubits in ``ancillas`` to decompose the gate into Toffoli gates (Lemmas 7.2 and 7.3 of Barenco et al., 1995). The ancillas are returned to their initial state, whatever it is. Without ancillas it falls back to :func:`control_decompose`. Args: circ: The circuit to push to. controls: The control qubits. target: The target qubit. ancillas: Qubits not involved in the gate, usable as workspace. Returns: The circuit ``circ``. """ from mimiqcircuits.operations.gates.standard.pauli import GateX from mimiqcircuits.operations.gates.standard.cnx import GateCCX from mimiqcircuits.operations.control import Control from mimiqcircuits.circuit import Circuit nctrl = len(controls) nq = nctrl + 1 + len(ancillas) if nctrl == 0: circ.push(GateX(), target) elif nctrl <= 2: circ.push(Control(nctrl, GateX()), *controls, target) elif nq >= 2 * nctrl - 1 and nctrl >= 3: # Decomposition according to Lemma 7.2 of [1] circ1 = Circuit() for i in range(nctrl - 3): circ1.push( GateCCX(), controls[-(i + 2)], ancillas[-(i + 2)], ancillas[-(i + 1)] ) circ2 = Circuit() circ2.push(GateCCX(), controls[0], controls[1], ancillas[-(nctrl - 2)]) circ3 = Circuit() circ3 = circ3.push(GateCCX(), controls[-1], ancillas[-1], target) circ.append(circ3) circ.append(circ1) circ.append(circ2) circ.append(circ1.inverse()) circ.append(circ3.inverse()) circ.append(circ1) circ.append(circ2) circ.append(circ1.inverse()) elif not len(ancillas) == 0: # Decomposition according to Lemma 7.3 of [1] m = nq // 2 free1 = list(controls[m:]) + [target] + list(ancillas[1:]) ctrl1 = controls[:m] trgt1 = ancillas[0] circ1 = Circuit() cx_decompose(circ1, ctrl1, trgt1, free1) free2 = list(controls[:m]) + list(ancillas[1:]) ctrl2 = list(controls[m:]) + [ancillas[0]] trgt2 = target circ2 = Circuit() cx_decompose(circ2, ctrl2, trgt2, free2) circ.append(circ1) circ.append(circ2) circ.append(circ1) circ.append(circ2) else: control_decompose(circ, GateX(), controls, target) return circ
[docs] def control_recursive_decompose(circ, operation, controls, target): """Push a multi-controlled ``operation`` to ``circ`` by recursion on its square root. Follows Barenco et al. (1995): the gate with ``n`` controls is built from singly-controlled square roots of ``operation``, multi-controlled X gates, and the same construction with ``n - 1`` controls. Args: circ: The circuit to push to. operation: A single-qubit gate. controls: The control qubits, at least two. target: The target qubit. Returns: The circuit ``circ``. """ from mimiqcircuits.operations.control import Control N = len(controls) V = operation.power(1 / 2) Vdag = V.inverse() circ.push(Control(1, V), controls[-1], target) # here target can be used as a free qubit cx_decompose(circ, controls[:-1], controls[-1], [target]) circ.push(Control(1, Vdag), controls[-1], target) # here target can be used as a free qubit cx_decompose(circ, controls[:-1], controls[-1], [target]) if N == 2: circ.push(Control(N - 1, V), controls[:-1], target) else: control_recursive_decompose(circ, V, controls[:-1], target) return circ
[docs] def rccx(circ, a, b, t): """Relative-phase Toffoli. A Toffoli up to a diagonal phase on its three qubits, with 4 T gates. It is its own inverse. """ from mimiqcircuits.operations.gates.standard.cpauli import GateCX from mimiqcircuits.operations.gates.standard.hadamard import GateH from mimiqcircuits.operations.gates.standard.t import GateT, GateTDG circ.push(GateH(), t) circ.push(GateT(), t) circ.push(GateCX(), b, t) circ.push(GateTDG(), t) circ.push(GateCX(), a, t) circ.push(GateT(), t) circ.push(GateCX(), b, t) circ.push(GateTDG(), t) circ.push(GateH(), t) return circ
[docs] def cnx_ladder(circ, controls, target, ancillas): """C_n(X) with m clean ancillas, m <= n - 2. The ladder stores in ancilla i the AND of the first i+1 controls. The remaining controls and the last ancilla control the target, then the ladder is undone. The relative phases of the ladder cancel: they are diagonal, and the middle gate only reads the ladder qubits. With m < n - 2 the middle gate still has 3 or more controls; it borrows the qubits the ladder has already read, which sit idle meanwhile. """ from mimiqcircuits.circuit import Circuit from mimiqcircuits.operations.annotations import AncillaAlloc, AncillaFree m = len(ancillas) for a in ancillas: circ.push(AncillaAlloc(), a) ladder = rccx(Circuit(), controls[0], controls[1], ancillas[0]) for i in range(1, m): rccx(ladder, ancillas[i - 1], controls[i + 1], ancillas[i]) rest = list(controls[m + 1 :]) circ.append(ladder) cx_decompose( circ, [ancillas[m - 1]] + rest, target, list(controls[: m + 1]) + list(ancillas[: m - 1]), ) circ.append(ladder.inverse()) for a in ancillas: circ.push(AncillaFree(), a) return circ
[docs] def and_compute(circ, a, b, t): """Logical AND of ``a`` and ``b`` into ``t``, which must be in ``|0>``. The relative-phase Toffoli leaves a phase i on ``|111>`` only, among the states it reaches from t = 0; the S-dagger removes it. """ from mimiqcircuits.operations.gates.standard.s import GateSDG rccx(circ, a, b, t) circ.push(GateSDG(), t) return circ
[docs] def and_uncompute(circ, a, b, t, bit): """Undo ``and_compute(circ, a, b, t)`` by measurement, without T gates. Measured in the X basis, ``t`` gives a random bit; when it is 1 the state has picked up a phase -1 where a and b are both 1, which a CZ conditioned on the bit undoes. The reset returns ``t`` to ``|0>``. """ from mimiqcircuits.bitstrings import BitString from mimiqcircuits.operations.gates.standard.cpauli import GateCZ from mimiqcircuits.operations.gates.standard.hadamard import GateH from mimiqcircuits.operations.ifstatement import IfStatement from mimiqcircuits.operations.measurereset import MeasureReset circ.push(GateH(), t) circ.push(MeasureReset(), t, bit) circ.push(IfStatement(GateCZ(), BitString("1")), a, b, bit) return circ
[docs] def cnx_measured_ladder(circ, controls, target, ancillas, bit): """C_n(X) with m clean ancillas, m <= n - 1, and a bit to measure into. As :func:`cnx_ladder`, but each step is an exact AND, undone by measurement. """ from mimiqcircuits.operations.annotations import AncillaAlloc, AncillaFree m = len(ancillas) steps = [ (controls[0] if i == 0 else ancillas[i - 1], controls[i + 1], ancillas[i]) for i in range(m) ] for a in ancillas: circ.push(AncillaAlloc(), a) for a, b, t in steps: and_compute(circ, a, b, t) rest = list(controls[m + 1 :]) cx_decompose( circ, [ancillas[m - 1]] + rest, target, list(controls[: m + 1]) + list(ancillas[: m - 1]), ) for a, b, t in reversed(steps): and_uncompute(circ, a, b, t, bit) for a in ancillas: circ.push(AncillaFree(), a) return circ