7

This question is two-fold and considers general $n$-qubit operations on a quantum computer.

First, can a general $n$-qubit operation be implemented on a quantum computer without the use of ancilla qubits?

Second, can ancilla qubits help in reducing the depth of such general $n$-qubit operations and if yes, what is the relation between the two?

glS
  • 24,708
  • 5
  • 34
  • 108
nippon
  • 1,517
  • 8
  • 22
  • 1
    This is definitely a good question, I think we need some more background info to contextualize it. For example, is it okay to approximate the n-qubit operation with error? What is our gate set? Do you have specific classes of operations in mind? – C. Kang Sep 17 '20 at 20:21
  • 1
    It would be interesting to know the difference between an approximation with error and an exact decomposition. For the gate-set, assume Pauli, H, CNOT, S, T, i.e., the 'standard' gate set. No specifics on the operations itself is assumed, though partial answers for specific operations are also useful. – nippon Sep 18 '20 at 06:38
  • 3
    Have you looked at the Solovay Kitaev algorithm? I believe it discusses this problem more https://arxiv.org/abs/quant-ph/0505030 – C. Kang Sep 18 '20 at 14:45

1 Answers1

3

I'll assume you're interested in unitary, n-qubit operations. Then yes, any universal gate-set can approximate any given unitary, even though some unitaries may require an exponential number of gates for this. The Solovay-Kitaev theorem gives a constructive proof, so it gives a concrete algorithm to find a sequence of operations from the universal gate-set that approximates any given unitary to an arbitrary distance. (There are some technical requirements, such as the need for the inverse of all gates in the gate-set.)

If you're interested in exactly obtaining the unitary, then not all gate-sets are equivalent. This is the realm of quantum circuit synthesis. In this case, as in the approximate case, sometimes auxiliary qubits can decrease the gate-count or the depth of the resulting circuit. As an example, check these exact decompositions of Toffoli gates, with and without auxiliary qubits: https://arxiv.org/abs/0803.2316

Ernesto Galvão
  • 295
  • 2
  • 6