5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you wanting this T operation to be independent of the circuit? $\endgroup$ – DaftWullie Nov 11 '18 at 10:50
  • $\begingroup$ That's not necessary, assuming U is some specific universal circuit that can simulate other circuits. $\endgroup$ – akvadrako Nov 11 '18 at 13:46
  • $\begingroup$ So $T^{-1}UT=U^{-1}$ for all U being used? The group of all the $U$ you are using would be abelian in that case. $\endgroup$ – AHusain Nov 11 '18 at 15:13
  • $\begingroup$ @AHusain, I think that's equivalent. $\endgroup$ – akvadrako Nov 12 '18 at 2:09
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's certainly interesting if this is the optimal strategy for a generic $U$. It would have been nice to find an efficient method for any circuit. $\endgroup$ – akvadrako Nov 13 '18 at 4:50
2
$\begingroup$

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).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the pointer and this might be useful to research the reverse myself. But they don't discuss reversing the computation. It's not clear how one might go about building T. $\endgroup$ – akvadrako Nov 12 '18 at 2:19
  • $\begingroup$ Sure, because that’s not the point of the paper. To calculate T, you just work out how to program the circuit and its inverse. Both are just sequences of 0s and 1s. T is simply the application of a bit flip in whichever positions those two sequences are different. (If the two sequences are different lengths, pad the shorter one with identity operations.) $\endgroup$ – DaftWullie Nov 12 '18 at 5:54
  • $\begingroup$ That's trivially true though. You have a universal circuit, so any behavior can be produced by some sequence of bits. $\endgroup$ – akvadrako Nov 12 '18 at 8:57
  • $\begingroup$ Sure, it's trivial once you're talking about a universally programmable circuit. But that's an unusual construction (because people typically talk about using universal gates to build a specific circuit). And it answers your question, as I understand it. $\endgroup$ – DaftWullie Nov 12 '18 at 10:26
  • $\begingroup$ It doesn't - I can't even tell if T is the same for different inputs. $\endgroup$ – akvadrako Nov 12 '18 at 12:13

Your Answer

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

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