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 a yong, maslov or gray 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 the compile 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 and yong. The default is auto.

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 and jones 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 keyword compile_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