Probabilistic exact construction of decoders from encoding black boxes

Isometry operations encode the quantum information of the input system to a larger output system, while the corresponding decoding operation would be the inverse operation.

Given an encoding operation as a black box from a d-dimensional system to a D-dimensional system, we propose a universal isometry inversion protocol that constructs a decoder from multiple calls of the encoding operation. This is a probabilistic but exact protocol whose success probability is independent of D. For a qubit (d=2) encoded in n qubits, our protocol achieves an exponential improvement over any tomography-based or unitary-embedding method, which cannot avoid D-dependence. We also discover a fundamental difference between isometry inversion and unitary inversion by showing a no-go theorem for isometry complex conjugation.