If you'll allow me to generalize a tiny bit... Let's extend the question and ask for other complexity-theoretic hardness assumptions and their consequences for scientific experiments. (I'll focus on physics.) Recently there was a rather successful program to try to understand the set of allowable correlations between two measurement devices which, while spatially separated, perform a measurement on a (possibly non-locally correlated) physical system (1). Under this and similar setups, one can use the assumptions about the hardness of communication complexity to derive tight bounds which reproduce the allowable correlations for quantum mechanics.
To give you a flavor, let me describe an earlier result in this regard. A Popescu-Rohrlich box (or PR box) is an imaginary device which reproduces correlations between the measurement devices which are consistent with the principle that no information can travel faster than light (called the principle of no signaling).
S. Popescu & D. Rohrlich, Quantum
nonlocality as an axiom, Found. Phys.
24, 379–385 (1994).
We can see this as an instance of communication complexity having some influence. The idea that two observers must communicate implicitly assumes some constraint which a physicist would call no signaling. Turning this idea around, what types of correlations are possible between two measurement devices constrained by no signaling? This is what Popescu & Rohrlich study. They showed that this set of allowable correlations is strictly larger than those allowed by quantum mechanics, which are in turn strictly larger than those allowed by classical physics.
The question then presents itself, what makes the set of quantum correlations the "right" set of correlations, and not those allowed by no signaling?
To address this question, let's make the bare-bones assumption that there exist functions for which the communication complexity is non-trivial. Here non-trivial just means that to jointly compute a boolean function f(x,y), it takes more than just a single bit (2). Well surprisingly, even this very weak complexity-theoretic assumption is sufficient to restrict the space of allowable correlations.
G. Brassard, H. Buhrman, N. Linden, A.
A. Méthot, A. Tapp, and F. Unger,
Limit on Nonlocality in Any World in
Which Communication Complexity Is Not
Trivial, Phys. Rev. Lett. 96, 250401
Note that a weaker result was already proven in the Ph.D. thesis of Wim van Dam. What Brassard et al. prove is that having access to PR boxes, even ones which are faulty and only produce the correct correlation some of the time, enables one to completely trivialize communication complexity. In this world, every two-variable Boolean function can be jointly computed by transmitting only a single bit. This seems pretty absurd, so let's look at it conversely. We can take the non-triviality of communication complexity as an axiom, and this allows us to derive the fact that we don't observe certain stronger-than-quantum correlations in our experiments.
This program using communication complexity has been surprisingly successful, perhaps much more so than the corresponding one for computational complexity. The papers above are really just the tip of the iceberg. A good place to begin further reading is this review:
H. Buhrman, R. Cleve, S. Massar and R.
de Wolf, Nonlocality and communication
complexity, Rev. Mod. Phys. 82,
or a forward literature search from the two other papers that I cited.
This also raises the interesting question about why the communication setting seems much more amenable to analysis than the computation setting. Perhaps that could be the subject of another posted question on cstheory.
(1) Take for example the experiments measuring something known as the CHSH inequality (a type of Bell inequality), where the physical system consists of two entangled photons, and the measurements are polarization measurements on the individual photons at two spatially distant locations.
(2) This single bit is necessary whenever f(x,y) actually depends on both x and y, since sending zero bits would violate no signaling.