Reversible computation without inverting the circuit

Question

I know that if you have a circuit $U$ that transforms $A → B$, it's possible to construct an inverse, ${U\dagger}(B) → A$. Is it also possible to transform the states with $T_{i,o}$ so that I can use the original circuit to do the reverse computation? Like so:

$$ U(T_o(B)) → T_i(A) $$

For example, I know the Toffoli gate is its own inverse. So $T_{i,o}$ can be the identity function:

$$U_{\operatorname{Tof}}(A) → B$$ $$U_{\operatorname{Tof}}(I(B)) → I(A)$$

I would like to know if some reasonable $T$ functions exists when $U$ is a universal circuit.

I'm a quantum computing newbie and coming at this question more from a physics standpoint, so not sure quite sure how to ask this most clearly. Suggestions are appreciated. Links to related research would also be great.

EDIT: $T$ may differ for input and output states.

Answer 1

This paper gives a fairly complete answer to the question "given oracle access to U, implement the inverse of U".

https://arxiv.org/abs/1810.06944

They give a protocol which implements U inverse with a number of queries that's linear in the dimension of U and show that this is essentially optimal.

This seems to be fairly closely related to your question. I think that you could transform a good protocol for your problem into a good protocol for their problem, which means that the lower bound in their paper would carry over to your setting. I'm not sure, though.

Answer 2

You might like to look up about quantum cellular automata. These are systems where you can repeatedly apply the same global unitary operation to generate the circuit that you want. The circuit is specified by the initial (product) state that is operated on. In that sense, you achieve the inverse using the same sequence of unitaries, just by changing the initial state in order to specify the inverse gate sequence. Thus, T will just be a sequence of bit flips.

This paper might be helpful: https://arxiv.org/abs/quant-ph/0502143

I guess that, overall, this only gives $$ U(T(B))=A, $$ rather than $U(T(B))=T(A)$, as desired.

There is a special class of unitaries (aside from the obvious $U=U^\dagger$) that can be inverted in the right sort of way. Imagine that $U$ is created by Hamiltonian evolution where the interactions are of the form $(XX+YY)$ between pairs of qubits. Let us further restrict to the case where the interactions are bipartite in nature, meaning that there is a consistent two-colouring of qubits such that every pair of qubits that are interacting under such a Hamiltonian term have different colours. (A one-dimensional chain with nearest-neighbour interactions, for example.) In this case, $T$ can be a $Z$ gate on every qubit or one particular colour, because $Z_1e^{-i(XX+YY)t}Z_1=e^{i(XX+YY)t}$. I don't know if any Hamiltonians which are universal for quantum computation satisfy a property such as this (certainly, they can be nearest-neighbour in a 1D chain).