qrisp.mcx#
- mcx(controls, target, method='auto', ctrl_state=-1, num_ancilla=1)[source]#
Applies a multi-controlled X gate.
The following methods are available:
Method
Description
gray
Performs a gray code traversal which requires no ancillae but is rather inefficient for large numbers of control qubits.
gray_pt
/gray_pt_inv
More efficient but introduce extra phases that need to be uncomputed by performing the inverse of this gate on the same inputs. For more information on phase tolerance, check this paper.
balauca
Method based on this paper with logarithmic depth but requires many ancilla qubits.
maslov
Documented here, requires less ancilla qubits but is only available for 4 or less control qubits.
yong
Can be found int this article.This method requires only a single ancilla and has moderate scaling in depth and gate count.
amy
A Toffoli-circuit (ie. only two control qubits are possible), which (temporarily) requires one ancilla qubit. However, instead of the no-ancilla T-depth 4, this circuit achieves a T-depth of 2. Find the implementation details in this paper.
jones
Similar to
amy
but uses two ancilla qubits, and has a T-depth of 1. Read about it here.gidney
A very unique way for synthesizing a logical AND. The Gidney Logical AND performs a circuit with T-depth 1 to compute the truth value and performs another circuit involving a measurement and a classically controlled CZ gate for uncomputation. The uncomputation circuit has T-depth 0, such that the combined T-depth is 1. Requires no ancillae. More details here. Works only for two control qubits.
hybrid
A flexible method which combines the other available methods, such that the amount of used ancillae is customizable. After several
balauca
-layers, the recursion is canceled by either ayong
,maslov
orgray
mcx, depending on what fits the most.auto
Recompiles the mcx gate at compile time using the hybrid algorithm together with the information about how many clean/dirty ancillae qubits are available. For more information check
qrisp.QuantumSession.compile()
.Note
Due to Qrisp’s automatic qubit management, clean ancilla qubits are not as much of a sparse resource as one might think. Even though the
balauca
method requires a considerable amount of ancillae, many other functions also do, implying there is alot of recycling potential. The net effect is that in more complex programs, the amount of qubits of the circuit returned by thecompile method
increases only slightly.- Parameters:
- controlslist[Qubits] or QuantumVariable
The Qubits to control on.
- targetQubit
The Qubit to perform the X gate on.
- methodstr, optional
The synthesis method. Available are
auto
,gray
,gray_pt
,gray_pt_inv
,maslov
,balauca
andyong
. The default isauto
.- ctrl_stateint or str, optional
The state on which to activate the X gate. The default is “1111..”.
- num_ancillaint, optional
Specifies the amount of ancilla qubits to use. This parameter is used only if the method is set to
hybrid
. The default is 1.
Examples
We apply a 3-contolled X gate
>>> from qrisp import QuantumVariable, mcx >>> control = QuantumVariable(3) >>> target = QuantumVariable(1) >>> mcx(control, target, method = "gray") >>> print(control.qs)
QuantumCircuit: -------------- control.0: ──■── │ control.1: ──■── │ control.2: ──■── ┌─┴─┐ target.0: ┤ X ├ └───┘ Live QuantumVariables: --------------------- QuantumVariable control QuantumVariable target
We compare different performance indicators.
from qrisp import QuantumVariable, mcx def benchmark_mcx(n, methods): for method in methods: controls = QuantumVariable(n) target = QuantumVariable(1) mcx(controls, target, method = method) compiled_qc = controls.qs.compile() print(f"==================\nMethod: {method}\n------------------") print(f"Depth: \t\t\t{compiled_qc.depth()}") print(f"CNOT count: \t{compiled_qc.cnot_count()}") print(f"Qubit count: \t{compiled_qc.num_qubits()}")
>>> benchmark_mcx(4, methods = ["gray", "gray_pt", "maslov", "balauca", "yong"]) ================== Method: gray ------------------ Depth: 50 CNOT count: 30 Qubit count: 5 ================== Method: gray_pt ------------------ Depth: 34 CNOT count: 16 Qubit count: 5 ================== Method: maslov ------------------ Depth: 43 CNOT count: 18 Qubit count: 6 ================== Method: balauca ------------------ Depth: 22 CNOT count: 18 Qubit count: 7 ================== Method: yong ------------------ Depth: 77 CNOT count: 30 Qubit count: 6 >>> benchmark_mcx(10, methods = ["gray", "gray_pt", "balauca", "yong"]) ================== Method: gray ------------------ Depth: 3106 CNOT count: 2046 Qubit count: 11 ================== Method: gray_pt ------------------ Depth: 2050 CNOT count: 1024 Qubit count: 11 ================== Method: balauca ------------------ Depth: 53 CNOT count: 54 Qubit count: 18 ================== Method: yong ------------------ Depth: 621 CNOT count: 264 Qubit count: 12
Mid circuit measurement based methods
The
gidney
andjones
method are unique in the way that they require mid circuit measurements. The measurements are inserted retroactively by the.compile
method, because immediate compilation would prevent evaluation of the statevector (since a measurement is involved).Instead a tentative (measurement free) representative is inserted and replaced at compile time.
To get a better understanding consider the following script:
>>> from qrisp import QuantumVariable, mcx >>> control = QuantumVariable(2) >>> target = QuantumVariable(1) >>> mcx(control, target, method = "jones") >>> print(control.qs) QuantumCircuit: --------------- ┌───────────────────────────┐ control.0: ┤0 ├ │ │ control.1: ┤1 ├ │ │ target.0: ┤2 uncompiled_jones_toffoli ├ │ │ jones_ancilla.0: ┤3 ├ │ │ jones_ancilla.1: ┤4 ├ └───────────────────────────┘ Live QuantumVariables: ---------------------- QuantumVariable control QuantumVariable target
We see that there is no classical bit and therefore also no measurement. The statevector can still be accessed:
>>> print(control.qs.statevector()) |00>*|0>
To introduce the measurement we simply call the
.compile
method with the keywordcompile_mcm = True
:>>> qc = control.qs.compile(compile_mcm = True) >>> print(qc) ┌─────────────────────────┐ control.0: ┤0 ├ │ │ control.1: ┤1 ├ │ │ target.0: ┤2 ├ │ compiled_jones_toffoli │ workspace_0: ┤3 ├ │ │ workspace_1: ┤4 ├ │ │ cb_0: ╡0 ╞ └─────────────────────────┘
Because there is a measurement now, the statevector can no longer be accessed.
>>> qc.statevector_array() Exception: Unitary of operation measure not defined.
However the T-depth went down by 50%:
>>> print(qc.t_depth()) 1 >>> print(control.qs.compile(compile_mcm = False).t_depth()) 2
A similar construction holds for the Gidney’s temporary logical AND. However there are additional details: This technique always comes in pairs. A computation and an uncomputation. The computation circuit has a T-depth of 1 and the uncomputation circuit has a T-depth of 0. The uncomputation circuit however contains a measurement.
As you can imagine, this measurement is also inserted at compile time.
Even though both circuits are not the inverses of each other, Qrisp will use the respective partner if called to invert:
>>> control = QuantumVariable(2) >>> target = QuantumVariable(1) >>> mcx(control, target, method = "gidney") >>> print(control.qs) QuantumCircuit: --------------- ┌────────────────────────┐ control.0: ┤0 ├ │ │ control.1: ┤1 uncompiled_gidney_mcx ├ │ │ target.0: ┤2 ├ └────────────────────────┘ Live QuantumVariables: ---------------------- QuantumVariable control QuantumVariable target
This even works in conjunction with the uncomputation module:
>>> target.uncompute() >>> print(target.qs) QuantumCircuit: --------------- ┌────────────────────────┐┌────────────────────────────┐ control.0: ┤0 ├┤0 ├ │ ││ │ control.1: ┤1 uncompiled_gidney_mcx ├┤1 uncompiled_gidney_mcx_inv ├ │ ││ │ target.0: ┤2 ├┤2 ├ └────────────────────────┘└────────────────────────────┘ Live QuantumVariables: ---------------------- QuantumVariable control
To introduce the measurement, we call the compile method.
>>> print(target.qs.compile(compile_mcm = True)) ┌──────────────────────┐┌──────────────────────────┐ control.0: ┤0 ├┤0 ├ │ ││ │ control.1: ┤1 compiled_gidney_mcx ├┤1 ├ │ ││ compiled_gidney_mcx_inv │ workspace_0: ┤2 ├┤2 ├ └──────────────────────┘│ │ cb_0: ════════════════════════╡0 ╞ └──────────────────────────┘
Apart from uncomputation, the inverted Gidney mcx can also be accessed via, the InversionEnvironment:
from qrisp import invert control = QuantumVariable(2) target = QuantumVariable(1) with invert(): mcx(control, target, method = "gidney")
>>> print(control.qs) QuantumCircuit: --------------- ┌────────────────────────────┐ control.0: ┤0 ├ │ │ control.1: ┤1 uncompiled_gidney_mcx_inv ├ │ │ target.0: ┤2 ├ └────────────────────────────┘ Live QuantumVariables: ---------------------- QuantumVariable control QuantumVariable target