Fast Tests for Probing the Causal Structure of Quantum Processes
629
5 Other Examples of Speedups in the Identification
of Causal Hypotheses
5.1 Multiple Candidates for the Causal Intermediary
In the previous sections, we have seen how to identify the causal intermediary of
a variable A among two possible candidates B and C. What about more than two
candidates? For k > 2 candidates, the derivation is technically more involved, but
the main results remain unchanged:
• In the classical case, when causal relations are described by arbitrary permutations, the minimal error probability is given by
p
C
err,k =
(k − 1)
2d N −1 + O(d
−2N ) ,
(22)
and the decay rate is log d.
• In the quantum case, parallel strategies without a reference system achieve error
probability
p
Q
err,k =
(k − 1)
2d N + O(d
−2N ) ,
(23)
and the decay rate is still log d. In contrast, parallel strategies using entanglement
with an external reference system can achieve a doubled decay rate 2 log d.
5.2 Detection of Causal Link Between Two Variables
A basic example of identification of causal hypotheses is to determine whether there
is a causal link between two variables A and B. In this case, the task is to determine
whether B is a causal intermediary for A, or whether B fluctuates at random
independently of A. As it turns out, entanglement with a reference system can once
again double the decay rate of the error probability: the classical error probability
decays with rate log d, while the quantum error probability with reference systems
decays with doubled rate 2 log d.
5.3 Identification of the Cause of a Variable
Another interesting problem is to identify which variable in a given set {A 1 , · · · A m }
is the cause for a given variable B (assuming that one and only one variable can be
the cause). Again, we assume that causal relation is induced by a reversible process
629
5 Other Examples of Speedups in the Identification
of Causal Hypotheses
5.1 Multiple Candidates for the Causal Intermediary
In the previous sections, we have seen how to identify the causal intermediary of
a variable A among two possible candidates B and C. What about more than two
candidates? For k > 2 candidates, the derivation is technically more involved, but
the main results remain unchanged:
• In the classical case, when causal relations are described by arbitrary permutations, the minimal error probability is given by
p
C
err,k =
(k − 1)
2d N −1 + O(d
−2N ) ,
(22)
and the decay rate is log d.
• In the quantum case, parallel strategies without a reference system achieve error
probability
p
Q
err,k =
(k − 1)
2d N + O(d
−2N ) ,
(23)
and the decay rate is still log d. In contrast, parallel strategies using entanglement
with an external reference system can achieve a doubled decay rate 2 log d.
5.2 Detection of Causal Link Between Two Variables
A basic example of identification of causal hypotheses is to determine whether there
is a causal link between two variables A and B. In this case, the task is to determine
whether B is a causal intermediary for A, or whether B fluctuates at random
independently of A. As it turns out, entanglement with a reference system can once
again double the decay rate of the error probability: the classical error probability
decays with rate log d, while the quantum error probability with reference systems
decays with doubled rate 2 log d.
5.3 Identification of the Cause of a Variable
Another interesting problem is to identify which variable in a given set {A 1 , · · · A m }
is the cause for a given variable B (assuming that one and only one variable can be
the cause). Again, we assume that causal relation is induced by a reversible process