5

The diamond norm categorises the single-use distinguishability of two quantum channels. The operational setting is the following: you have access to an unknown unitary, which is promissed to be either $U_1$ or $U_2$ and the goal is to distinguish whether you are in the case where you have $U_1$ or in the case where you have $U_2$.

Is there an efficiently computable measure for the setting of distinguishing channels when we are allowed to make two or more uses of the channel? In other words, is there an algorithm for efficiently computing the maximum probability of success for identifying which channel we have, given $k$ uses of the channel, for any $k$?

I encountered a related question on the tensor product of many copies of the unitary. However this assumes that the copies of the unitary are applied to a probe state in parallel. I think it does not capture all strategies that may query the probe state in sequence, or use an adaptive strategy based on measurements. Moreover the discussion there is only about an upper bound.

It seems that this is a more difficult problem. Harrow et al (2010) found an example of a channel that can be distinguished perfectly with two uses in an adaptive strategy, but for which no finite number of uses without an adaptive strategy would be sufficient for perfect distinguishing.

shashvat
  • 847
  • 5
  • 13

2 Answers2

2

It is possible to compute the maximum success probability for discriminating two channels given $k$ adaptive uses through semidefinite programming — specifically through the so-called quantum strategies or quantum combs framework. In short, strategies/combs are basically multiple-use channels with memories.

Here are the original references on the framework itself. You should be able to find many follow-up papers by chasing references through Google Scholar.

  • Gus Gutoski and John Watrous. Toward a general theory of quantum games. In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007), pages 565–574, 2007. arXiv:quant-ph/0611234

  • Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. Quantum circuit architecture. Physical Review Letters 101(6): 060401, 2008. arXiv:0712.1325

  • Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. Theoretical framework for quantum networks. Physical Review A 80(2):022339, 2009. arXiv:0904.4483

The specific topic of channel discrimination is considered from the viewpoint of this framework in these papers:

  • Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. Memory effects in quantum channel discrimination. Physical Review Letters 101:180501, 2008. arXiv:0803.3237

  • Gus Gutoski. On a measure of distance for quantum strategies. Journal of Mathematical Physics 53(3), 2012. arXiv:1008.4636

To connect these papers to the specific problem of $k$ uses of a given channel, note that this is just a special case of a strategy/comb where there doesn't happen to be an actual memory. It is, in fact, possible to solve the problem suggested in the question through semidefinite programming when the things being discriminated are themselves strategies/combs (i.e., channels with memory).

John Watrous
  • 6,342
  • 18
  • 28
1

What you're looking for is a tester, an object that can encode any possible discrimination strategy, including adaptive ones. Then to calculate the maximum probability of distinguishing two channels, you need to optimize over the tester. This optimization problem turns out to be an SDP.

The answer is therefore yes, there does exist an algorithm, and it is efficient. One must be however careful with the meaning of efficient: the complexity is polynomial on the dimension of the problem, which is great, but the dimension of the problem grows exponentially with the number of copies of the channels, so the algorithm can only be run for small cases. Symmetrization techniques are needed to tackle larger problems, as done for example here and here.

Mateus Araújo
  • 3,112
  • 9
  • 20