Each possible update path can be stimulated in linear time (or is it polynomial? It depends how you measure the cost of searching for a location to apply the up

Each possible update path can be stimulated in linear time (or is it polynomial? It depends how you measure the cost of searching for a location to apply the update rules, and weather the update rules are fixed), but stimulating the full multiway system has unbounded complexity in the general case. The reason they suspect that quantum computers will not provide an inherent speedup has to do with the cost of "completion", i.e. measurement, which is explicit and finite in these models.