1. Introduction

There is a distinction that is sometimes made in the scholarship on scientific explanation between explaining why and explaining ‘how-possibly’. In the ontic context, where the explanations one gives aim at describing salient features of actual physical systems, the former is sometimes also called ‘how-actually’ explanation. That how-actually explanation actually explains is uncontroversial; however, it is less clear just what if any explanatory merit there is in explaining how some event possibly came about. Partly for this reason, the literature on how-possibly explanation is comparatively sparse, and the few who have commented on the topic are of varying opinion with regard to its virtues. While some view how-possibly explanation as genuinely explanatory, others have argued that how-possibly ‘explanation’ is better thought of as a mere heuristic device and not as constituting genuine explanation at all. Still others have thought of how-possibly explanation as a kind of incomplete how-actually explanation—a stepping-stone on the way to the how-actually explanation that one ultimately seeks.

Below I consider a question that I will argue sheds light on this issue. It is drawn from the science of quantum computation. Quantum computation is a fruitful merger of the fields of physics and computer science, and one of the goals of this science is to determine the source of the power of quantum computers, that is, to search for the explanation of the fact that quantum computers can in general (and sometimes dramatically) outperform classical computers. What I will argue is the following: to answer this question is to compare algorithmic processes of various kinds and, in so doing, to describe the possibility spaces associated with these processes. By doing this, we explain how it is possible for one process to outperform its rival. Further, and importantly, in examples like this little if anything is gained in subsequently asking a how-actually question. Once one has answered the how-possibly question, there is little left to do.

I will close by suggesting that the search for the explanation of the power of quantum computation is just one example of a species of how-possibly question that is likely to be found in many other sciences as well.

2. How-Possibly Explanation

The first mention of how-possibly explanation is likely that of Dray (Reference Dray1957). Dray’s primary goal in that book is to assess the adequacy of the ‘covering law model’ of explanation for characterizing historical explanation. The model is so called because it involves the subsumption of a particular set of initial conditions under a law or a set of laws (Hempel Reference Hempel1965). Dray’s verdict is that the covering law model fails to capture many interesting senses of historical explanation. One of the ways in which the covering law model is inadequate, according to Dray, is that it insists that any explanation of a given fact must show why, necessarily, that fact had to occur, since the statement of the fact to be explained must be deductively entailed by the statements of the relevant laws and initial conditions.Footnote ¹ Dray insists, however, that not all historical explanations are why-necessarily explanations:

What is explained here, for Dray, is not exactly why the ball landed in the center fielder’s glove. Rather, what is dispelled is the initial puzzlement on the part of the listener upon hearing the announcement. This puzzlement is removed once she is told of the scorekeeper’s ladder, for the ladder explains how the catch was possible: it opens up a range of possibilities that would not have been present otherwise. Of course, one can still ask, “Why, exactly, did the ball land in his glove?” However, to do so, for Dray, is to ask a logically different question. The how-possibly question is answered once we have been told about the ladder.

Hempel’s covering law model, with its exclusive emphasis on why-necessarily questions, was, for many years, the ‘received view’ on scientific explanation. But although similar conceptions continue to be defended, there is no longer a near consensus, and indeed many have taken a pluralistic attitude (or at any rate remained agnostic) on the question of whether an all-encompassing model of scientific explanation exists.Footnote ² Despite this, how-possibly explanation in particular has received comparatively little attention, but it has received some. There are those, for instance, who reject outright the very idea of how-possibly explanation—Reiner (Reference Reiner1993, 68) goes so far as to call its promotion and proliferation a “sociological risk”—however, the majority of the debate surrounding how-possibly explanation centers around the sense and extent to which it (in Dray’s or perhaps some other formulation) is explanatory.Footnote ³

Thus, even Hempel grants to Dray that there is some sense in which a how-possibly account explains. Nevertheless, he argues, upon hearing it, the questioner will invariably desire to be told why the event necessarily occurred if he is to be fully satisfied (Hempel Reference Hempel1965, 429). For Hempel, the role of how-possibly explanation is primarily pragmatic: it motivates the questioner to ask a further why-necessarily question. For Resnik (Reference Resnik1991, 143), on the other hand, how-possibly and how-actually explanations are of the same kind and differ only in the degree to which they are empirically supported. That is, a how-possibly explanation is a how-actually explanation that enjoys no more than speculative supporting evidence yet nevertheless displays other explanatory virtues such as fruitfulness.

Forber (Reference Forber2010), in contrast, views how-possibly and how-actually explanations as different in kind. What Resnik refers to as how-possibly explanation is, for Forber, no more than an incomplete how-actually explanation. Explaining how-possibly, for Forber, is not this but a kind of formal inquiry: given a set of relevant background assumptions, one deduces (e.g., via computer simulation) a particular set of outcomes reachable from them.Footnote ⁴ For instance, let the assumptions consist of known biological laws relevant to a particular population, plus a specification of a set of variable parameters, and let the different outcomes represent various genotypes associated with that population. Then, when one runs such a simulation, the different paths by which it arrives at a particular outcome carve up the possibility space for that outcome—they represent a set of how-possibly explanations corresponding to it.Footnote ⁵ Explaining how-actually, in contrast, is a form of empirical inquiry: its aim is to determine which of these possibilities is the actual one.

A further mode of how-possibly explanation, described by Persson (Reference Persson, de Regt, Hartmann and Okasha2012, 275), “aims to establish the existence of a mechanism by which X could be, and was, generated without filling in all the details.” Key to Persson’s conception is the empirical determination of the actually existing mechanism responsible for X. It is thus distinct from Resnik’s conception of how-possibly explanation as inadequately supported how-actually explanation. It is also distinct from Forber’s conception of how-possibly explanation, which, recall, is not a form of empirical inquiry at all. Nevertheless, it is how-possibly and not how-actually explanation because, although one describes an actual mechanism responsible for X, information is missing from the description of the mechanism that would allow one to determine the precise (typically causal) pathway by which X was brought about. Thus, one has not given an account of how the event actually occurred.

In the modes of explaining how-possibly identified so far, the questioner is required, or at any rate it is perfectly sensible for her, to continue on to ask the how-actually question. Thus, for Hempel she (at least in interesting cases; see Hempel Reference Hempel1965, 429) will not be fully satisfied until she answers the how-actually question. On Resnik’s conception, how-possibly explanations are just how-actually explanations that have not been adequately confirmed, and it goes without saying that we should try to confirm them. For Persson it is not confirming but “filling in” of the mechanism that remains to be done. In Forber’s conception, explaining how-possibly is in no way inferior to explaining how-actually, yet both play an essential role in our inquiries into phenomena. For Dray, pace Hempel, sometimes one is thoroughly satisfied with a how-possibly explanation. Nevertheless, it is perfectly sensible to go on and ask exactly how the center fielder caught the ball once he was at the top of the platform.

The kind of how-possibly explanation I describe in the next section bears resemblances to both Persson’s and Forber’s conceptions. As in Persson’s conception, it involves the description of some mechanism actually responsible for producing an outcome. Unlike in Persson’s conception, in this case there are no relevant details of the mechanism left to fill in.

On the other hand, the way the mechanism explains, as in Forber’s conception, is that it deductively carves out a particular possibility space for an outcome. But unlike all of the conceptions reviewed above, once one has answered the how-possibly question in this case, it is doubtful that a how-actually explanation can give us anything more of substance.Footnote ⁶

3. Explaining ‘Quantum Speedup’

A basic distinction, in computational complexity theory, is between those computational problems amenable to an efficient solution in terms of time and/or space resources and those that are not. Easy (or ‘tractable’, ‘feasible’, ‘efficiently solvable’, etc.) problems have solutions that involve resources bounded by a polynomial in the input size, n (n is typically the number of bits used to represent the input). Hard problems are those that are not easy, that is, they require resources that are ‘exponential’ in n, that is, that grow faster than any polynomial in n (Nielsen and Chuang Reference Nielsen and Chuang2000, 139).Footnote ⁷ For example, a problem that requires approximately n^c time steps to solve in the worst case (for some constant c) is tractable according to this definition. A problem that requires approximately cⁿ steps, on the other hand, is said to be intractable.

‘Quantum speedup’ refers to the fact that some computational problems can be solved exponentially faster with a quantum computer than with any known classical computer.Footnote ⁸ For example, the fastest known classical algorithm for factoring the product of two unknown primes is exponential in n. Shor’s quantum algorithm, astoundingly, solves the problem in polynomial time (Nielsen and Chuang Reference Nielsen and Chuang2000, 216). But while the fact of quantum speedup is almost beyond doubt, its source is still a matter of debate within the scientific community.Footnote ⁹ According to Fortnow (Reference Fortnow2003), for instance, the explanation of quantum speedup lies in the ability of quantum systems to exhibit ‘interference’. For Ekert and Jozsa (Reference Ekert and Jozsa1998), on the other hand, it is their ability to exhibit ‘entanglement’.

We will consider these candidate explanations in a little more detail later. For now let us ask, what kind of question is one asking when one asks to have quantum speedup explained? It is clearly an ontic question, for it aims to identify certain physical characteristics of particular kinds of systems. It is also a how question, that is, it inquires, specifically, about the distinctive mechanism by which quantum computers operate. It remains to consider whether it is a how-possibly or a how-actually question.

Consider figure 1, which depicts an instance of the SelectionSort algorithm for sorting a given list of integers. If given, say, the numbers (25, 12, 13, 19, 8), then after a certain time a computer running this code will produce (8, 12, 13, 19, 25). Now if we examine the algorithm, we notice that in the worst case (indeed, in any case) there will be n − 1 comparisons in the first iteration, n − 2 comparisons in the second, n − 3 in the third, and so on (where n is the number of list items). This gives a total of n(n − 1)/2 comparisons; thus, our total worst-case running time is ‘on the order of’ n ², or in symbols, O(n ²). SelectionSort is not the only algorithm for sorting integers. Both faster and slower algorithms exist. For instance, the MergeSort algorithm has a worst-case running time O(n log n) (Mehlhorn and Sanders Reference Mehlhorn and Sanders2008).Footnote ¹⁰

Figure 1. Set of instructions (in C) implementing the SelectionSort solution to the problem of sorting a list of given integers.

Suppose that we are comparing the running times of various algorithms. I feed random lists of n integers to a computer running SelectionSort, and you feed random lists of n integers to a computer running MergeSort. Yours takes O(n log n) steps to finish its sorts. Mine takes O(n ²) steps. What is the explanation for this difference in performance? Well, one way to explain it is just to point to the differences in the code for the two algorithms. But what does this code represent? Certainly, it does not represent one particular linear sequence of transitions, for both the ‘if’ and the ‘for’ loops encode conditional statements. Rather, it represents a space of possibilities—a set of pathways by which a computer can arrive at a particular result. It turns out that the pathways available to a computer implementing MergeSort allow a solution to be reached in fewer time steps than the pathways available to one implementing SelectionSort.

Something similar can be said when comparing different classes of machine. Consider, for instance, figure 2. ‘State transition diagrams’ such as this are essentially just another way of representing algorithms, although the representation they afford is somewhat ‘closer to the hardware’, so to speak. The machine depicted is an example of a deterministic finite automaton (DFA). It is not the only kind of computing machine. There are also, for instance, nondeterministic finite automata, deterministic and nondeterministic ‘pushdown’ automata, and deterministic and nondeterministic Turing machines, to name a few. To define these various classes of machine, we describe the possible states and state transitions that they are capable of. For example, DFAs are characterized by a finite set of states, deterministic transitions between states, and the lack of any form of external storage (see Martin Reference Martin1997).

Figure 2. State diagram representation of a deterministic finite automaton (DFA). Binary strings of variable length are input to the automaton. They are ‘accepted’ if the machine is found to be in the state a after the last character has been read. This particular machine will accept any string ending in ‘10’.

Given our characterizations of different types of machine, we can inquire about the set of problems computable by the machines of a particular class. It turns out, for example, that DFAs are severely limited with respect to the class of problems they are capable of solving, while Turing machines, in contrast, are capable of solving any effectively calculable function. We can similarly ask about the resources required to solve particular classes of computational problems by machines of a particular sort. We can ask, for instance, about the class of problems solvable by a deterministic Turing machine in polynomial time, about those solvable by a nondeterministic Turing machine in exponential time, and so on. Answering these and other similar questions will involve appealing to the states and to the state transitions that are possible for a particular class of machine. This state space, we will say, allows us to construct such a machine to realize an algorithm that will solve the problem in a given amount of time.

The question “What is the source of quantum speedup?” is a question of just this sort. Quantum computers are just another type of computational machine, and just as for Turing machines and DFAs, quantum computers have associated with them a particular space of states and a particular way of transitioning between states. In order to answer the question “What is the source of quantum speedup?” therefore, we will appeal precisely to the quantum mechanical state space and to the allowable transitions within it, and we will consider these in comparison to the space of states and state transitions possible for a classical computer. And when we do so, we will be explaining how it is possible that a quantum computer can outperform a classical one.

We see this, in fact, when we examine the approaches that those in the scientific community have taken to answering this question. Consider Fortnow (Reference Fortnow2003), for example, who develops an abstract mathematical framework for representing the computational complexity classes associated with both classical and quantum computing. In Fortnow’s framework, both kinds of computation are represented by transition matrices that determine the allowable transitions between possible configurations of a particular kind of machine. To represent the quantum case, Fortnow allows matrix entries to be negative as well as positive, while for the classical case they may only be positive. As a result, in the quantum case matrix entries will sometimes cancel each other out when summed; not so in the classical case. Fortnow shows that this suffices to capture the computational complexity classes associated with classical and quantum computing. According to Fortnow, this means that the fundamental difference between quantum and classical computation is that in quantum computation there can sometimes be interference between computational paths: “The strength of quantum computing lies in the ability to have bad computation paths eliminate each other thus causing some good paths to occur with larger probability” (Reference Fortnow2003, 606).Footnote ¹¹ Ekert and Jozsa (Reference Ekert and Jozsa1998), on the other hand, argue that the fact that quantum systems can sometimes be in entangled states yields a state space for combined quantum systems that is exponentially larger than the state space associated with combined classical systems.Footnote ¹² And while it is possible to, in a roundabout way, simulate this larger state space with a classical computer, the resource cost of doing so scales exponentially (Ekert and Jozsa Reference Ekert and Jozsa1998, 1771).Footnote ¹³

But is this really explaining how-possibly? Isn’t it the case, one might object, that an algorithm like SelectionSort is a description of how a system actually goes about solving a problem, and likewise that a description of the state space and state transitions associated with a particular class of system is a description of the actual resources used by those systems? These mechanisms are actually being employed, are they not? Of course, this is true, in the same way that Dray’s center fielder actually used the ladder to make the catch. But the latter is not a how-actually explanation, and neither are the former. For Dray the role played by a description of the ladder in the explanation of the fielder’s catch is to dispel the questioner’s puzzlement regarding how the catch was possible, without explaining exactly how it happened (or why it was necessary). But why does the ladder dispel her puzzlement? It does so because pointing out that a ladder was present opens up a whole new range of possibilities for the questioner that simply weren’t there before. Likewise in the cases we are considering: the algorithms, or the state spaces, as the case may be—considered not as ‘black boxes’, but in detail—explain by explicitly specifying the set of possibilities open to them.Footnote ¹⁴

But is the how-possibly explanation fully satisfactory? Shouldn’t we feel the urge to continue our investigation until we have found the actual path taken by the computer through its state space? Let us consider what this would mean in the case of the performance comparison between SelectionSort and MergeSort. In this case we would presumably (assuming that the precise input values were known) answer the how-actually question by giving a detailed description of the states of the computers after each time step, and after counting up all the transitions, we would see that mine took l steps and yours took k. In the context of a discussion of the performance characteristics of different types of computer, however, it is not clear what such an answer will add to our understanding of these processes. Such an answer, in that context, seems to do little more than restate the original question. It is in the description of their possibility spaces—the alternatives encoded in the conditional statements in figure 1, or in the edges of figure 2—that the information about the performance characteristics of my and your computer is most crucially contained. But by describing these possibility spaces, we answer not a how-actually but a how-possibly question. It is the latter question that is the critical one in the context of this investigation.

4. Conclusion

The kind of how-possibly explanation I have described in this paper bears certain resemblances to both Forber’s and Persson’s conceptions of explaining how-possibly. As in Persson’s conception, an explanation of the comparative performance characteristics of quantum and classical computers involves, I have argued, a description of the actual mechanisms associated with these machines. The description of a mechanism serves to carve out a particular possibility space for a machine, and as in Forber’s view, this possibility space plays a crucial role in a how-possibly explanation of the computationally relevant characteristics of that machine. I have further argued that, unlike other interesting examples previously given in the literature on this form of explanation, once one has answered this how-possibly question, it is doubtful that continuing on to ask a how-actually question can yield anything more of substance.

The kind of how-possibly question I have described here is characteristic not only of the inquiry into the source of quantum speedup but also of the sciences of computability and computational complexity theory generally—and not just this. Algorithmic processes abound in nature: in biological systems, in cognitive systems, and also in physical systems, to name but a few. Questions regarding their comparative performance characteristics likewise abound. And I would argue, if I had the space, that all of these questions are most appropriately answered by explaining how-possibly.