1
$\begingroup$

It is known that the "unbounded quantum fanout operation" is very powerful: (See, for example, Hoyer et al. : http://theoryofcomputing.org/articles/v001a005/v001a005.pdf).

In particular, it is known that many operations that cannot be done in constant depth classical circuits can be done in constant depth quantum cicuits that include the quantum fan-out operation.

However, I can't seem to find any discussion as to whether "constant depth" fanout is possible physically.

In classical computation, it seems fairly reasonable to consider "fan-out" to be an operation that does not add to the "depth" of a circuit: such a computational model models the latency of actual physical circuits of reasonable size.

For a fair comparison, unbounded quantum fanout would need to be achievable using some kind of experiment with a latency that scales as a constant with the size of the fanout (if it scales even logarithmically, then that kind of defeats the whole advantage of the quantum fanout operation).

Is there any experimental evidence to suggest whether such constant-latency quantum fanout unitary operations are feasible?

$\endgroup$
  • 3
    $\begingroup$ You're comparing apples and oranges. Unbounded fanout is not experimentally feasible in classical computation. It's a pretty good model for certain reasonably-sized circuits. It's also not experimentally feasible in quantum computation. The question is: how good a model is it? $\endgroup$ – Peter Shor Feb 4 '16 at 14:56
2
$\begingroup$

There are two way to see your question :

  1. Is unbounded fanout a reasonable approximation for realistic (quantum) circuits ?
  2. Is there a realistic quantum architecture which is effectively equivalent to the quantum circuit with unbounded fan-out ?

Peter Shor essentially suggested the formulation 1. in his comment above, and I’ll let experimentalists answer this question.

The question 2. seems strange, but I bring it forward because its answer is positive : In a 2009 paper (arXiv:0909.4673, paywalled version), Dan Browne, Elham Kashefi, and Simon Perdrix showed that Measurement Based Quantum Computing (MBQC), is equivalent up to a classical side-processing of logarithmic depth, to the quantum circuit model augmented with unbounded fanout gates.

They basically recall that the unbounded parity gate is a Clifford gate and can be therefore be expressed as a measurement pattern of constant depth (arXiv,paywalled PRA) and show that a fanout gate is nothing else than a parity gate “sandwiched” between two layers of Hadamard gates, and can therefore be simulated in constant depth.

Therefore, your question

Is there any experimental evidence to suggest whether such constant-latency quantum fanout unitary operations are feasible?

is equivalent to

Is there any experimental evidence to suggest whether Measurent Based Quantum Computing is feasible?

I personally think the answer to the latter question is “yes”, but the opinions on the feasibility of a given quantum computing architecture tend to be subjective...

$\endgroup$

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.