In the paper Implementing Grover oracles for quantum key search on AES and LowMC, the authors use a different construction of AND gate and its adjoint rather than the Toffoli gate to decrease the T-depth at the expense of 1 extra qubit. I am trying to implement the adjoint circuit in Qiskit which is shown in the figure. enter image description here

This is my implementation in Qiskit

q = QuantumRegister(3)
c = ClassicalRegister(1)
qand_dg = QuantumCircuit(q,c)

enter image description here

I converted this to instruction and tested it. For values 00, 01, 10, 11 (using NOT gates), I add a Toffoli gate and then add qand_dg instruction. Below is the code for testing.

for i in range(4):
    x = bin(i)[2:].zfill(2) # Convert number to binary with 2 bits
    qc = QuantumCircuit(3,4) 
    # Encode the value of x in the quantum circuit
    for index, j in enumerate(x):
        if j == '1':
    qc.toffoli(0,1,2) # Apply the toffoli gate
    qc.append(qand_dg_gate, range(3),[0]) # Apply the quantum and adjoint instruction
    qc.measure([0,1,2],[1,2,3]) # Measure the qubits
    # Simulate
    counts = execute(qc, backend=simulator, shots=shots).result().get_counts(qc)
    res = list(counts.keys())[0][::-1] # Result
    actual = x + str(int(x[0])&int(x[1])) # expected result
    print(res, actual)

This gives different outputs on different runs.

  1. enter image description here

  2. enter image description here

Can anyone help me understand this behaviour?

I also tried implementing the circuit in a different way using the controlled operation. Circuit is shown below:

enter image description here

This also had the same problem. Moreover, this circuit's T-depth is 6 calculated using the below method

qc_t = transpile(qc, basis_gates=['cx','x', 'h','t','tdg','s','sdg'])
print("T-depth:",qc_t.depth(lambda gate: gate[0].name in ['t', 'tdg']))

Why T-depth is 6 having no T-gates?

I used the following code to see the transpiled circuit:

qc_t = transpile(qc, basis_gates=['cx','x', 'h','t','tdg','s','sdg'])
print("T-depth:",qc_t.depth(lambda gate: gate[0].name in ['t', 'tdg']))

The output is this:

Without decomposing quantum and gate:
Depth: 8
Width: 4
Size: 8
Operations: OrderedDict([('s', 2), ('cx', 2), ('h', 1), ('measure', 1), ('x', 1), ('sdg', 1)])

After decomposing quantum and gate:
Depth: 8
T-depth: 6
Width: 4
Size: 8
Operations: OrderedDict([('s', 2), ('cx', 2), ('h', 1), ('measure', 1), ('x', 1), ('sdg', 1)])

Drawing the transpiled version of the circuit, the output is the same as the original one.

  • $\begingroup$ Have you looked at the transpiled circuit qc_t? There must be T gates there, and they are likely to not be very optimal btw. $\endgroup$ May 25, 2022 at 13:55
  • $\begingroup$ Edited the question @NikitaNemkov $\endgroup$ May 25, 2022 at 16:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.