<p>Is there any known result regarding the hardness of the following problem:</p>

<blockquote>
  <p>Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that implements the same unitary.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2018-09-25T12:45:57.323Z
You may be aware of this paper about the classical reversible case https://www.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 https://pdfs.semanticscholar.org/1b20/84b07cb5d1aa3496562cfdc9c958baae2c3b.pdf which gives a space efficient classical simulation of quantum computation
Joseph Van Name
CC BY-SA 4.0
2018-09-26T08:43:47.383Z
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?
John
<np-hardness><quantum-computing><quantum-information><reversible-computing>
Hardness of ancilla free quantum circuit extraction from circuit with ancillas
John
# Hardness of ancilla free quantum circuit extraction from circuit with ancillas

(Asked by: username_0 on 2018-09-25)

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.

**Tags:** np-hardness, quantum-computing, quantum-information, reversible-computing

> **Comments:**
> **username_1**: You may be aware of this paper about the classical reversible case https://www.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 https://pdfs.semanticscholar.org/1b20/84b07cb5d1aa3496562cfdc9c958baae2c3b.pdf which gives a space efficient classical simulation of quantum computation  
> **username_0**: 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?  

---

## 0 answers

