A circuit needs a NOT gate controlled by three qubits, (sometimes drawn as a single…

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch The quantum circuit model

Problem

A circuit needs a NOT gate controlled by three qubits,

C^3(X)

(sometimes drawn as a single multiply-controlled gate but built here from Toffolis and CNOTs). Using the standard construction of

C^n(U)

from

n-1

ancilla qubits,

2(n-1)

Toffoli gates and one two-qubit controlled-

U

, with

n=3

controls and

U=X

(so the final controlled-

U

is itself a single CNOT): ((a)) how many ancilla qubits are needed? ((b)) how many Toffoli gates are used? ((c)) if each Toffoli is compiled into six CNOT gates (ignoring single-qubit gates), how many CNOT gates does the whole

C^3(X)

cost in total, including the final CNOT?

Browse the problem library