2
$\begingroup$

DaftWullie mentions an interesting point here:

let's assume that we know an efficient classical computation of $f(x)$. That means we can build a reversible quantum computation that runs in the same time.

Questions:

  1. What exactly is meant by efficient "classical computation" here? Does it mean something like the Volder's algorithm for implementing trigonometric, hyperbolic and exponential functions?

  2. Say, we know how to implement $\sin^{-1}(x)$ using a CORDIC-based digital circuit (with registers, multiplexers, adders and all that). Can we build an equivalent quantum circuit that has the same computational complexity as its digital counterpart? If yes, how?

  3. How do we prove that the time complexities of the digital and quantum counterparts are equal (or nearly equal)?

$\endgroup$
2
  • $\begingroup$ I read @DaftWullie's comment as "if we know how to synthesize $f(x)$ efficiently with a number of irreversible $\mathsf{NAND}$ gates, $\mathsf{NOR}$ gates, etc, then we have an efficient process for synthesizing $f(x)$ with an efficient number of reversible $\mathsf{XOR}$ gates, $\mathsf{XNOR}$ gates, $\mathsf{CNOT}$, etc." Here "efficient" means polynomial in the number of bits of $x$. $\endgroup$ Apr 27, 2019 at 13:16
  • $\begingroup$ @MarkS Well yes, that's what I suspected too. However, in digital logic design (for combinatorial as well as sequential circuits), it's rare to use classical gates directly. Higher level components like multiplexers, registers, adders, subtractors, etc. are used instead (that's basically what the CORDIC implementation does). And in the case of the HHL (in the linked question), they're specifically talking about the implementation of the arcsine. Anyway, a proof at the level of classical logic gates (AND, OR, NAND, etc.) should be good enough for showing equivalent complexities. $\endgroup$ Apr 27, 2019 at 13:21

1 Answer 1

3
$\begingroup$

DaftWullie's comments aren't special to 'efficiently computable' functions $f(x)$ — any function at all which we know how to compute by conventional means, we can compute reversibly with at most a (small!) constant factor overhead.

How to reversibly compute a function

The proof is simple. For any procedure to compute something conventionally — classically and without regard to reversibility — we can suppose that it is described in terms of a circuit consisting of FANOUT, NOT, XOR, and AND gates. (If you prefer a different set of universal logic gates, a very slightly different proof can easily be found for that gate set — but it is important that we explicitly account for when we make copies of a bit, which is what we use FANOUT for.) Then we can stimulate each of the gates FANOUT, XOR, and AND using CNOT and TOFFOLI gates as follows: $$\begin {aligned} \mathrm{FANOUT} (a)& = \mathrm{CNOT} (a, 0) \\ \bigl(a, \mathrm{XOR} (a, b) \bigr) & = \mathrm{CNOT} (a, b) \\ \bigl(a, b, \mathrm{AND} (a, b) \bigr) & = \mathrm{TOFFOLI} (a, b, 0) \end {aligned} $$ Thus it takes exactly one of either CNOT or TOFFOLI (and possibly a fresh bit with the value 0) to simulate the computation of a single FANOUT, XOR, or AND gate.

Composing these in the appropriate way, we can compute any classical function that we know how to compute, using only reversible gates.

  • If (as is usually the case for quantum computation) the TOFFOLI or CNOT operations are not primitive operations of your computational model, the more important thing is that it be possible to realise those operations somehow. If you can decompose them into a fixed size sequence of primitive operations, then doing the computation reversibly only requires an overhead up to some constant factor, i.e. the size of the most complicated decomposition of those reversible gates. For quantum circuits, it is reasonable to suppose that this factor is at most 15 (which is not wonderful, but from a theoretical standpoint is also not terrible, and can be improved depending on what operations you allow).

  • This reversible realisation of the computation may require some extra workspace: a number of bits which is at most the number of logic gates in your procedure. In some cases, there may be cleverer ways to reversibly realise the computation which requires fewer additional bits than this: coming up with the most sparing such reversible realisation is not necessarily easy.

On efficient functions

The above remarks apply in principle to any classical circuit construction, and indeed to the primitive operations in any higher-level gate model (e.g. the CORDIC-based circuits of your question or any digit-extraction algorithm to compute some function). In principle, given a modest amount of (sufficiently high quality) additional memory, we can simulate any such circuit on a gate-by-gate basis to provide reversible equivalents with the same number of gates, or nearly so.

For more complicated functions, there is ironically enough more opportunities to save on the additional workspace required, which are impossible for the simpler gates (because those gates are too simple to provide opportunities to save) — economies of scale become possible, though not guaranteed.

The important part is that, additional workspace aside, these realisations will respect most notions of 'efficiency'. It does not increase the depth or size of the circuit by more than a constant factor, if at all. If you care about polynomial-size, linear-size, poly-log-depth, what-have-you — this simulation method preserves it.

$\endgroup$
3
  • $\begingroup$ Thanks, that clarifies a bit. One issue: when they say that the quantum circuit "runs in the same time" do they actually mean "has similar circuit depth as the corresponding classical circuit"? I mean, I'm not clear on what is really being compared when they say "time taken to compute $f(x)$". How do we theoretically model the "time"? Is there a notion of circuit complexity for quantum circuits as well, which makes them comparable to digital logic circuits, in terms of computation time? $\endgroup$ Apr 27, 2019 at 13:35
  • 1
    $\begingroup$ If you care about clock time, obviously any theoretical promise of exactly the same time cannot hold. Here I expect we're talking either about depth or size, and up to constant factors (or exactly if you count TOFFOLI as a primitive gate) for simulating e.g. NAND circuits with extra bits with values 0 or 1. (Size / Depth for reversible circuits and quantum circuits is computed much as for conventional logic circuits, and are well-respected concepts.) Any more precise promise will surely depend on the technology involved, and won't be a very general theoretical guarantee. $\endgroup$ Apr 27, 2019 at 13:40
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ Apr 27, 2019 at 14:55

Your Answer

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

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