7
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – C. Kang
    Sep 17, 2020 at 20:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – nippon
    Sep 18, 2020 at 6:38
  • 3
    $\begingroup$ Have you looked at the Solovay Kitaev algorithm? I believe it discusses this problem more arxiv.org/abs/quant-ph/0505030 $\endgroup$
    – C. Kang
    Sep 18, 2020 at 14:45

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.