The expectation values of a predetermined set of Pauli observables can be predicted using only a few copies of a quantum state. However, when later observables depend on earlier predictions, how the system size constrains the required number of copies remains unclear. We use classical interactive fingerprinting codes to establish this constraint. A compact Pauli-parity encoding embeds the fingerprinting interaction into the quantum prediction task, allowing any quantum prediction mechanism on the constructed diagonal states to be simulated by a classical response strategy subject to the same information constraints. We show that accurate prediction from too few copies would violate the guarantees of the fingerprinting code. For n qubits and M adaptively chosen Pauli observables, requiring all predictions to be simultaneously accurate to a fixed additive error with probability at least 2/3 yields the worst-case lower bound N∗(n,M)=Ω(min{n,M}) on the required number of copies. For M≤n, this lower bound matches known upper bounds. In particular, n adaptive predictions require Θ(n) copies, whereas the same number of predetermined queries requires only O(logn) copies. This separation persists even for diagonal states and commuting observables.
Quantum channels can be characterized by their action on an orthogonal operator basis, where these operators are related to observable properties of the quantum system. For qudit and multimode bosonic systems, this is encoded respectively in the Heisenberg--Weyl transfer matrix estimated from the Choi-state, and in the characteristic-function transfer map estimated from a two-mode squeezed vacuum based Choi-state. We derive sample-complexity bounds for estimating entries of the transfer matrix/map to additive accuracy ε with success probability ≥1−δ, under different resources: access to the complex-conjugate channel E∗ and/or parallel access to c copies. In all settings, the learner uses parallel channel calls with adaptively chosen, ancilla-assisted input states and measurements. Absolute values of transfer-matrix entries can be learned efficiently with simultaneous access to E and E∗, with tight scaling ε−4. Without conjugate access, any c<d copies are insufficient for efficient learning, requiring sample complexity exponential in the number of (d-level) qudits n (for prime d). Efficiency is recovered at c=d, with tight scaling ε−2d. For bosonic systems, exponential sample complexity holds in terms of an effective dimension induced by an energy constraint for all c=O(1/ε). Although the task is learning a particular state, these bounds carry stronger implications than standard state-learning bounds since the learner controls the inputs and has ancillary assistance. This establishes a hierarchy of channel-learning resources: self-complex-conjugate channels require two-copy ancilla-assisted access for efficient learning, while for every square-free d, some channels require d-copy access. As a corollary, we derive tighter lower bounds for state learning with limited multi-copy access.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth.
We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential.
The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy.
Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension d and M≥d2−1 ports, we construct a unitary circuit of depth O(d), independent of M and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2. Thus, at fixed d, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on d can also be removed remains open.