If we could only get two-qubit tomography as an output, what algorithms are possible

According to the circuit model, the output for a quantum computation on $$n$$ qubits is an $$n$$-bit string. But what if we instead got a full two qubit tomography for all $$n(n-1)$$ pairs of qubits?

This would need to be calculated over many shots. If we simple used 1 shot, then we could easily just read out the resulting bit string. If we had infinite shots, and hence arbitrarily accurate tomography, perhaps we'd get some undesirable superpowers. Let's rule out both with the restriction that the number of shots must be both upper and lower bounded by $$\textrm{poly}(n)$$.

For algorithms with deterministic outputs, all shots give the same output. So in these cases, we'll still just be able to read out the standard result.

For algorithms with random outputs (like Shor's which gives random factors), things might be more tricky.

So what kinds of algorithms could be run with this restriction? And what kind of speed-ups could be obtained?

• so you mean an algorithm whose output is the full tomography of the input state? How would you store such an output? Taking as an example two-qubit inputs, the number of output qubits will have to depend on the precision with which you want to estimate the input, no? Or are you considering an "algorithm" in the more general sense of a quantum-classical procedure, where you store the tomography output in classical memories? But then, aren't you just asking what can be done when you can do full state tomography of a state? – glS May 22 at 11:25
• Not a tomography of the input state, but of the output state. And not a full tomography, but one that only captures the two qubit correlations. So (for the case of all measurements delayed until the end), instead of being given a histogram of bit strings you are given all the two qubit Pauli expectation values. – James Wootton May 23 at 20:35
• isn't that akin to asking what can be done when you regard doing (partial?) tomography as a free operation? Or you mean a more abstract scenario in which we "magically" can access (partial) tomographic information about the state? Like, in the latter case we could for example store and reliably retrieve an infinite amount of information even using a single qubit I guess – glS May 24 at 11:05