PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum computations without definite causal structure

G. Chiribella, G. M. D'Ariano, P. Perinotti, B. Valiron

arXiv:0912.0195v4quant-ph

TL;DR

The paper asks whether every higher-order transformation of black boxes can be realized by inserting them into a circuit with fixed causal order. It develops supermaps on restricted channel sets and analyzes the SWITCH, showing that admissible transformations can require indefinite causal structure, while fixed-order simulation may need postselection or extra queries.

  • Problem

    The paper addresses whether all physically admissible transformations of black boxes can be implemented by inserting the boxes into a circuit with a pre-defined causal order.

  • Method

    The paper develops higher-order supermaps on no-signalling and product channels and analyzes classical and quantum SWITCH transformations.

  • Results

    The SWITCH is admissible but cannot be realized by inserting one use of the input black boxes into a fixed-order quantum circuit; fixed-structure simulations require postselection or an extra query.

  • Takeaways & Limitations

    The quantum switch is a new computational primitive in which the causal structure of connections can be in a quantum superposition.

Abstract

from arXiv · show

We show that quantum theory allows for transformations of black boxes that cannot be realized by inserting the input black boxes within a circuit in a pre-defined causal order. The simplest example of such a transformation is the classical switch of black boxes, where two input black boxes are arranged in two different orders conditionally on the value of a classical bit. The quantum version of this transformation-the quantum switch-produces an output circuit where the order of the connections is controlled by a quantum bit, which becomes entangled with the circuit structure. Simulating these transformations in a circuit with fixed causal structure requires either postselection, or an extra query to the input black boxes.

I. INTRODUCTION

The paper extends quantum computation from processing states through time to higher-order transformations of black-box operations. It introduces the SWITCH as a counterexample to realization by ordinary circuits with fixed causal ordering and reviews the circuit framework used to analyze it.

  • I. INTRODUCTION: Higher-order quantum computation transforms input black-box operations into output operations, generalizing computation beyond the time evolution of quantum states.This framework is motivated by computing functions of functions and includes ordinary state processing as a special case.
  • I. INTRODUCTION: The SWITCH arranges two black boxes A and B in either order, BA or AB, conditional on a control bit.Its quantum version allows the control qubit to become entangled with the circuit structure.
  • I. INTRODUCTION: The quantum circuit model represents information flow through wires and gates ordered from left to right, with no computational loops.Its rules include one box per use of a transformation, left-to-right input/output relations, and fixed computational resource accounting.
  • I. INTRODUCTION: The paper shows that some admissible higher-order computations cannot be implemented by inserting one use of each input black box into a fixed-order quantum circuit.For the classical SWITCH, deterministic circuit implementation is equivalent to access to a closed timelike curve.
  • I. INTRODUCTION: Ordinary deterministic supermaps are exactly transformations obtainable by inserting a single input channel into a suitable quantum circuit.Therefore, counterexamples must be sought among transformations acting on restricted channel sets rather than arbitrary individual channels.

C. Generalizations: hierarchy of higher-order maps and supermaps on restricted sets of channels

The paper generalizes supermaps to higher levels and to restricted channel sets, especially no-signalling channels, and establishes complete positivity under an internal-channel condition.

  • Hierarchy of higher-order maps: Higher-order maps can be iterated to transform quantum supermaps into supermaps, producing an infinite hierarchy of quantum maps.Part of this hierarchy has been characterized for transformations realizable within the quantum circuit framework.
  • Supermaps on restricted sets of channels: Supermaps can instead be defined on restricted channel sets, requiring valid outputs only for inputs in the chosen set and its bipartite extensions.The paper focuses on the restricted set of no-signalling channels.
  • Open problems: Complete characterization and physical interpretation of these generalized quantum maps remain open problems.This limitation applies both to the broader hierarchy and to supermaps acting on restricted channel sets.
  • Complete positivity: If the input restricted set contains an internal channel, the corresponding supermap is completely positive in the Choi representation.The completely depolarizing channel is an example of an internal channel, so the condition applies to the channel classes considered here.

E. Deterministic supermaps on no-signalling channels

For bipartite no-signalling channels, the paper proves that deterministic supermaps are equivalently characterized by their action on product channels. This equivalence supports the analysis of transformations such as the SWITCH.

  • No-signalling channels: A bipartite channel is no-signalling when each party’s reduced output depends only on that party’s reduced input through a local channel.The definition imposes the two marginal relations for all bipartite inputs.
  • Restricted supermaps: Supermaps on no-signalling channels have a weaker normalization requirement than ordinary supermaps, because validity is required only for no-signalling inputs.Consequently, the class is larger than ordinary circuit-realizable supermaps.
  • Equivalence theorem: The deterministic supermaps on no-signalling channels coincide one-to-one with deterministic supermaps on product channels.Two such supermaps that agree on every product channel also agree on every no-signalling channel.
  • Equivalence theorem: No-signalling channels can be represented as affine combinations of product channels, which underlies the equivalence theorem.The coefficients are real, while the component maps are local quantum channels.
  • Complete positivity: Supermaps on product channels preserve complete positivity even when applied locally to arbitrary completely positive maps.The proof uses the product of local depolarizing channels as an internal channel.

G. The switch supermap

The switch supermap uniquely produces a classically controlled ordering of two channels, while complete positivity constrains its action and supports an impossibility result for fixed-circuit realization.

  • Definition and action: The switch supermap Z maps two quantum channels to a channel that applies BA or AB according to a measurement of a control qubit.The control outcome determines which composition acts on the input system.
  • Uniqueness: Complete positivity, together with the switch action on product channels, uniquely determines the supermaps Z(0) and Z(1).The Choi representation and linearity establish this uniqueness.
  • Extension: The switch formula extends from quantum channels to arbitrary quantum operations QA and QB.The resulting action is Z(QA ⊗QB)(ρ) = QBQA(⟨0|Qρ|0⟩Q) + QAQB(⟨1|Qρ|1⟩Q).
  • Operator action: For arbitrary operators A and B, Z(0) maps their Choi rank-one operators to |AB⟩⟨AB|, whereas Z(1) maps them to |BA⟩⟨BA|.These identities are obtained by analyzing unitary channels and extending the result by linearity.
  • Scope: The impossibility proof for switching boxes in dimension d > 2 can be extended using shift-and-multiply unitaries.The qubit proof itself uses properties of Pauli matrices.

IV. NO GO THEOREM FOR THE CLASSICAL SWITCH OF BLACK BOXES

The SWITCH function conditionally connects two black boxes in opposite orders, but no deterministic fixed-order circuit can implement it with one call to each box. The proof reduces such a realization to deterministic time travel, yielding an impossibility result.

  • The SWITCH function connects black boxes A and B in orders BA or AB according to a classical control bit.
  • Ordinary circuits cannot reverse a chosen time-ordering between black boxes without effectively sending information back in time.
  • The no-go theorem states that SWITCH cannot be computed deterministically when the two unknown oracles are called once in a fixed causal order.
  • A deterministic circuit using one call to each unknown oracle would imply deterministic time travel.
  • For swap channels, the supposed implementation creates a time loop, representing an identity map from a future computational step to a previous one.
  • The contradiction can be formalized using probabilistic teleportation: the proposed construction would imply the absurd equality 1 = 4.
  • Access to a closed timelike curve is equivalent to deterministic circuit realization of SWITCH, and the impossibility extends to classical boxes.

V. WAYS AROUND THE NO-GO THEOREM

The no-go theorem depends on black-box access, one call per box, forbidden time loops, and determinism. Relaxing any of these requirements provides a route around the theorem.

  • The theorem assumes that f and g are supplied as black boxes.
  • The theorem assumes that each black box can be called only once during the circuit run.
  • The theorem assumes that time loops are forbidden.
  • The theorem assumes that the circuit is deterministic.
  • Relaxing any of these four requirements can provide a way around the no-go theorem.

A. Implementation of the program SWITCH via access to program states

The SWITCH program can be implemented using encoded program states, but only for black boxes that a programmable channel can encode and decode.

  • Program-state implementations can produce SWITCH outputs for black boxes that are encoded in a program system and decoded by a programmable channel R.
  • The program-state approach therefore does not cover arbitrary quantum black boxes.
  • The quantum no-programming theorem forbids encoding an arbitrary quantum channel in a finite program state.Two unitary channels can be retrieved from program states only when those states are orthogonal.

B. Implementation of the SWITCH program with two queries to the black boxes

A fixed-order circuit can realize SWITCH with two queries to at least one black box, whereas the single-call restriction prevents this construction for unknown oracles.

  • A computational circuit produces the SWITCH transformation by using two calls to at least one of the input oracles.
  • The construction uses a control-swap channel to exchange two input qubits according to the control qubit.
  • For black-box inputs, obtaining two uses from one use is ruled out by the no-cloning theorem for boxes.If the functions were known, they could be duplicated and used in the circuit construction.

C. Implementation of the program SWITCH through access to a closed timelike curve

A circuit with access to a closed timelike curve can implement SWITCH deterministically on arbitrary black boxes using only one call to each.

  • Access to a closed timelike curve lets a circuit implement SWITCH deterministically for arbitrary black boxes with one run of each black box.The closed timelike curve is described as an identity channel from the future to the past.

D. Probabilistic simulation of the SWITCH program with a single query to the black boxes

With one query to each black box, fixed-order circuits can simulate SWITCH probabilistically through teleportation, including a quantum superposition of the two orderings.

  • A probabilistic-teleportation circuit succeeds in implementing SWITCH with probability 1/4.
  • Conditioned on the teleportation outcome E, the circuit applies different box orders depending on the control qubit.
  • Putting the control qubit in superposition yields a superposition of the two box orderings.The output is proportional to (UfUg |ψ⟩|1⟩ + UgUf |ψ⟩|0⟩)/2.
  • For N input qubits per box, the maximum probabilistic-simulation success probability is pN = 4^-N.

VI. RE-MODELLING OF THE ORACLES IN ORDER TO ALLOW FOR THE CLASSICAL SWITCH

The paper enlarges the circuit model to represent classical and quantum control over the causal order of black-box operations. The quantum-controlled oracle cannot be implemented with fixed causal ordering or with the classically controlled oracle, while two queries simulate the quantum SWITCH.

  • No-go result: No fixed-order circuit using one call to each black box can deterministically implement SWITCH.The paper identifies the obstruction as incompatibility with any pre-defined causal ordering; time-loop realizations would be an alternative only by changing the circuit rules.
  • Classical switch: Classical control represents two successive black-box calls whose order is selected by a control bit.The corresponding oracle can be physically realized using movable connections and implements SWITCH.
  • Quantum switch: Quantum control preserves coherence in the control qubit and entangles it with the causal ordering of the boxes.This requires circuits with movable wires that may occupy quantum superpositions.
  • Quantum-controlled oracle: The quantum-controlled oracle W_f,g is defined for unitary and noisy channels and is independent of the chosen Kraus representations.Discarding its control qubit yields the classically controlled oracle O_f,g.
  • Simulation and information processing: Two queries to the input boxes simulate the quantum SWITCH, giving ordinary circuits an equivalent computation with only a factor-2 slowdown.Thus SWITCH does not increase complexity-theoretic power, although it can improve information-processing tasks such as channel discrimination.
  • Open problem: The physical implementation of arbitrary maps on product channels and higher-order maps remains open.Consequently, the computational power of higher-order computation has not been fully assessed.

VIII. CONCLUSIONS

The paper formalizes higher-order transformations of channels through the SWITCH, proves that fixed-order circuits cannot realize it with single black-box calls, and extends the model to classical and quantum causal control. It concludes that quantum control of causal structure is a new computational resource, while the broader theory and physical implementation of higher-order maps remain incomplete.

  • Results: Transformations of bipartite no-signalling channels can be equivalently defined as transformations of product channels, including SWITCH.SWITCH maps channels A and B to AB or BA depending on a control bit.
  • Results: SWITCH is a higher-order computation that no ordinary quantum circuit can implement deterministically with a single call to each box.The incompatibility is with every fixed causal ordering between A and B.
  • Workarounds: The paper discusses four ways around the no-go theorem, including program-state access, two queries, closed timelike curves, and probabilistic simulation.It also introduces classical control of causal sequences as a minimal oracle-model change.
  • Quantum switch: Quantum control of causal sequences implements the quantum SWITCH, allowing the connections' causal structure to exist in a quantum superposition.The authors relate this possibility to scenarios where space-time geometry is entangled with physical-system states.
  • Open scope: A complete physical theory of higher-order computation has not yet been developed.The paper proposes that further analysis may inform quantum gravity and related frameworks, but arbitrary higher-order computational power remains unresolved.

Appendix A: Proof of theorem 1

The appendix proves complete positivity of supermaps by using an internal channel, purification, and the Choi representation. It also presents quantum combs as a concise framework for characterizing fixed-causal-order realizations.

  • Proof of complete positivity: For a positive operator Q, the proof establishes positivity of the transformed operator (eS ⊗ I_C)(Q).Q is treated, after rescaling, as the Choi operator of a quantum operation.
  • Proof of complete positivity: Purifying the internal channel C0 ⊗ ρ0 produces an extension V whose Choi operator supports the positivity argument.The construction uses a full-rank state ρ0 and an auxiliary Hilbert space D.
  • Proof of complete positivity: Applying the supermap to the extension V yields a quantum channel, which implies complete positivity in the Choi representation.The final inequality follows from positivity of the transformed purification.
  • Quantum comb proof: Quantum combs represent a supermap as a completely positive map and then as a positive operator through recursive use of the Choi isomorphism.This formalism provides a short alternative proof of Theorem 3.
  • Fixed-order characterization: Fixed-order realizability is characterized by the existence of positive operators satisfying the circuit conditions for either A preceding B or B preceding A.The appendix states the corresponding necessary-and-sufficient conditions for both causal orders.
Loading 0912.0195v4…