The simulation of quantum effects requires certain classical resources, and quantifying them is an important step to characterize the difference between quantum and classical physics. For a simulation of the phenomenon of state-independent quantum contextuality, we show that the minimum amount of memory used by the simulation is the critical resource. We derive optimal simulation strategies for important cases and prove that reproducing the results of sequential measurements on a two-qubit system requires more memory than the information-carrying capacity of the system.
The simulation of quantum effects requires certain classical resources, and quantifying them is an important step to characterize the difference between quantum and classical physics. For a simulation of the phenomenon of state-independent quantum contextuality, we show that the minimum amount of memory used by the simulation is the critical resource. We derive optimal simulation strategies for important cases and prove that reproducing the results of sequential measurements on a two-qubit system requires more memory than the information-carrying capacity of the system.
Since quantum measurement is universal for quantum computation (Nielsen [3]), the minimization of the resources required for measurement‐based quantum computation is a crucial point ([3, 1, 4, 5, 6]). We have shown in [6] that a set of observables composed of one two‐qubit measurement and three one‐qubit measurements form a universal set for quantum computation if one ancillary qubit is available as an additional resource. This set is minimal in terms of two‐qubit measurements, because at least one multi‐qubit operation is needed to create entanglement, and is also minimal in terms of ancillary qubits, because at least one ancillary qubit is required to simulate reversible transformations with projective measurements only. We discuss in this paper the required number of one‐qubit measurements for a set of observables to be universal. A set composed of one two‐qubit measurement and only two one‐qubit measurements is proved universal, at the cost of a second ancillary qubit. Thus an additional ancillary qubit seems to be required to obtain a smaller universal set of measurements. One may conclude to a trade off between ancillary qubits and observables in measurement‐based quantum computation.
Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be
Θ(din3dout3/ε2), where
din and
dout are the channel input and output dimensions, respectively, and
ε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires
Ω(din3dout3/ε2) queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound
O(din3dout3/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case
din=1. By contrast, coherent protocols with quantum memory achieve query complexity
Θ(din2dout2/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
How much memory does a quantum device need to prepare systems one at a time? We address this question through the lens of quantum resource theories, which formalize physical restrictions on how the memory may interact with the stream of systems it processes. By comparing sequential with collective preparation, we show that under general assumptions both have the same asymptotic memory cost per output. Still, sequential preparation can require an unboundedly larger memory than collective one, and we investigate how this gap depends on the physical restrictions on the allowed interactions. For energy-conserving unitaries, we determine both optimal memory dimensions needed for preparing pure states from an energy eigenstate, and find that the extra memory required sequentially either remains bounded or grows logarithmically with the number of outputs. Under noisy operations, we reveal transformations for which one auxiliary qubit suffices for preparing arbitrarily many independent outputs collectively, while no memory of fixed dimension can deliver them sequentially. Finally, for sequential protocols that repeat a fixed interaction, we show that a
d-dimensional memory that succeeds for
d2 rounds will succeed forever, and that such a sequential preparation is equivalent to quantum catalysis.
Not all unitary operations upon a set of qubits can be implemented by sequential interactions between each qubit and an ancillary system. We analyze the specific case of sequential quantum cloning, 1-->M, and prove that the minimal dimension D of the ancilla grows linearly with the number of clones M. In particular, we obtain D=2M for symmetric universal quantum cloning and D=M+1 for symmetric phase-covariant cloning. Furthermore, we provide a recipe for the required ancilla-qubit interactions in each step of the sequential procedure for both cases.