# Quantum AND† gate

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. This is my implementation in Qiskit

q = QuantumRegister(3)
c = ClassicalRegister(1)
qand_dg = QuantumCircuit(q,c)
qand_dg.h(2)
qand_dg.measure(2,0)
if(c):
qand_dg.x(2)
qand_dg.s(1)
qand_dg.s(0)
qand_dg.cnot(0,1)
qand_dg.sdg(1)
qand_dg.cnot(0,1) 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.x(index)

qc.toffoli(0,1,2) # Apply the toffoli gate
qc.append(qand_dg_gate, range(3),) # 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())[::-1] # Result
actual = x + str(int(x)&int(x)) # expected result

print(res, actual)


This gives different outputs on different runs.

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: 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.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("Depth:",qc_t.depth())
print("T-depth:",qc_t.depth(lambda gate: gate.name in ['t', 'tdg']))
print("Width:",qc_t.width())
print("Size:",qc_t.size())
print("Operations:",qc_t.count_ops())


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.

• 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. May 25, 2022 at 13:55
• Edited the question @NikitaNemkov May 25, 2022 at 16:26