3
$\begingroup$

Is there any known result regarding the hardness of the following problem:

Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that implements the same unitary.

I'm assuming that the ancilla qubits are supplied in computational basis states. It might be that the result is different depending on whether the ancilla bits are required to be left clean. I seem to recall a result stating that the verification of an ancilla qubit being left clean is a hard problem, but I don't know the specifics.

A related problem would be to require the circuits to be reversible classical circuits. I don't think this problem is strictly a subset however, as the unitary without ancillae could take 'shortcuts' using quantum operations not available in classical reversible circuits.

Improve this question
$\endgroup$
2
  • $\begingroup$ You may be aware of this paper about the classical reversible case sciencedirect.com/science/article/pii/S0022000099916720 in which the authors establish that a T(n) time and S(n) space Turing machine can be simulated by a space S(n) reversible Turing machine with an exponential time tradeoff (i.e. one can emulate classical computation reversibly without playing Bennett's pebble game and using ancilla bits). I also found this paper pdfs.semanticscholar.org/1b20/… which gives a space efficient classical simulation of quantum computation $\endgroup$
    – Joseph Van Name
    Sep 25 '18 at 12:45
  • $\begingroup$ Thank you for those references. You can of course represent a quantum circuit with ancillae as a $2^n\times 2^n$ unitary matrix, and then use Solovay-Kitaev to synthesize an ancilla free equivalent circuit, but this takes exponential time. From perusing those papers it seems to me that they will also take exponential time to transform the circuit, or am I missing something? $\endgroup$
    – John
    Sep 26 '18 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.