# Continuous Quantum-Classical Transitions and Measurement: A Relook

Partha<EMAIL_ADDRESS>
The National Academy of Sciences, India,
5 Lajpatrai Road, Allahabad 211002, India

###### Abstract

The measurement problem in quantum mechanics originates in the inability of
the Schrödinger equation to predict definite outcomes of measurements. This is
due to the lack of objectivity of the eigenstates of the measuring apparatus.
Such objectivity can be achieved if a unified realist conceptual framework can
be formulated in terms of wave functions and operators acting on them for both
the quantum and classical domains. Such a framework was proposed and an
equation for the wave function written down ([13, 14]) which smoothly
interpolates between the quantum and classical limits. The arguments leading
to the equation are clarified in this paper, and the theory is developed
further. The measurement problem in quantum mechanics is then briefly reviewed
and re-examined from the point of view of this theory, and it is shown how the
classical limit of the wave function of the measuring apparatus leads to a
natural solution of the problem of definite measurement outcomes without the
need for either collapse or pragmatic thermodynamic arguments. This is
consistent with Bohr’s emphasis on the primacy of classical concepts and
classical measuring devices. Possible tests of the theory using low-
dimensional systems such as quantum dots are indicated.

##  1 Introduction

Quantum mechanics has been plagued by conceptual difficulties right from its
inception. Arguably the most important one of these is the measurement problem
originating in the inability of the Schrödinger equation to predict definite
outcomes of measurements. A definite outcome of a ‘measurement’ of a ‘micro
system’ in quantum mechanics requires a non-quantum mechanical observer, like
a ‘macroscopic classical apparatus’ or a ‘conscious observer’, and therefore a
“shifty split of the world into ‘system’ and ‘apparatus”’ that lacks
conceptual clarity in the absence of any parameter in the equation to
distinguish between quantum and classical states [1]. Some additional
hypotheses have been suggested to ‘solve’ the measurement problem, such as the
splitting of the universe into branches [2], the existence of hidden
trajectories (variables) in addition to the wave function [3, 4], spontaneous
collapse [5], etc. However, no universally accepted solution exists [6]. It is
also not clear in which sense, if any, this ‘incompleteness’ is related to
that emphasized by Einstein, Podolsky and Rosen [7].

There is a huge conceptual disconnect between a quantum mechanical and a
conventional classical description of a physical system. A multi-particle
system in classical mechanics is described by real particles moving in real
four-dimensional space-time, whereas a multi-particle system in quantum
mechanics is described by complex wave functions in a multidimensional
configuration space and spanning a Hilbert space. It is only in the case of a
single particle that the configuration space is identical with real space. The
ontology of classical physics is that of ‘realism’, whereas that of standard
quantum mechanics is a debatable issue [8, 9]. What is required therefore for
conceptual clarity is a single equation with a realist ontology that
interpolates smoothly between the quantum and classical descriptions. Since
quantum mechanics has been so immensely successful in describing the
microscopic entities that constitute classical systems like measuring
apparatus, it would seem reasonable first to attempt to formulate a similar
theory of classical mechanical systems based on a Hilbert space of states and
operators acting on the states. If that can be done, one would be in a better
position to explore the possibility of the required equation. Complex, square
integrable wave functions $\psi(q,p,t)$ for classical statistical mechanical
systems were, in fact, introduced way back in 1931-32 by Koopman [10] and von
Neumann [11] for this very reason [12]. The dynamical variables $p$ and $q$
are represented in this theory by commuting operators. They used the Liouville
equation for $\psi(q,p,t)$ and $\psi^{*}(q,p,t)$ and derived the classical
Liouville equation for the density $\psi^{*}\psi$ in phase space. In this
formulation the amplitude and phase of the classical wave function are
decoupled and interference effects are avoided. However, a smooth quantum-
classical connection is not easy to see in this theory because the underlying
dynamics is different in the two cases.

Here we propose to use a different equation of motion for the classical wave
function [13, 14] which is closer in form to the Schrödinger equation than the
Liouville equation. To see how one can arrive at such an equation, let us
first consider the Schrödinger equation

$\displaystyle i\,\hbar\,\frac{\partial\psi_{q}}{\partial t}$ $\displaystyle=$
$\displaystyle\left(-\frac{\hbar^{2}}{2m}\,\nabla^{2}+V\right)\psi_{q}$ (1)

for a quantum mechanical wave function $\psi_{q}$. Writing $\psi_{q}$ in the
polar form $\psi_{q}=R_{q}{\rm exp}(iS_{q}/\hbar)$ and separating the real and
imaginary parts, one gets the two coupled equations

$\displaystyle\partial S_{q}/\partial t+\frac{(\nabla S_{q})^{2}}{2m}+V+Q_{q}$
$\displaystyle=$ $\displaystyle
0,\,\,\,\,Q_{q}=-\frac{\hbar^{2}}{2m}\,\frac{\nabla^{2}R_{q}}{R_{q}},$ (2)
$\displaystyle\frac{\partial R_{q}^{2}}{\partial
t}+\vec{\nabla}\,.\,\left(\,R_{q}^{2}\,\frac{\vec{\nabla}S_{q}}{m}\right)$
$\displaystyle=$ $\displaystyle 0.$ (3)

It is obvious from these equations that apart from the term $Q_{q}$ (the
quantum potential), the first equation is identical with the classical
Hamilton-Jacobi equation for the action $S_{cl}$. Further, the second
equation, which is the continuity equation for the probability density
$R^{2}_{q}$, shows that if $R_{q}$ is chosen to be real at some initial time,
it would remain so for all future times. In the absence of the term $Q_{q}$
these two equations would therefore be decoupled, implying that the amplitude
$R_{cl}$ and the phase $S_{cl}/\hbar$ of a classical wave function $\psi_{cl}$
evolve independent of each other, ensuring the absence of observable
interference effects. Thus, in the absence of the term $Q_{q}$ the two
equations would be completely equivalent to the classical statistical
mechanics of a system of particles with a distribution function $R_{cl}^{2}$
obeying a continuity equation.

Notice that

$Q_{q}R_{q}=-\frac{\hbar^{2}\nabla^{2}R_{q}}{2m}=\frac{\hat{p}^{2}}{2m}R_{q},\,\,\,\,\hat{p}=-i\hbar\nabla,$
(4)

showing that the quantum potential $Q_{q}$ is the quantum mechanical kinetic
energy and is at the origin of the commutation relation
$\left[\hat{p},q\right]=-i\hbar$. Hence, the term $Q_{q}$ encapsulates in it
all quantum mechanical effects.

The task therefore is to write an additional term in the Schrödinger equation
that will exactly cancel the quantum potential. With this in view, consider
the equation

$\displaystyle i\,\hbar\,\frac{\partial\psi_{cl}}{\partial t}$
$\displaystyle=$
$\displaystyle\left(-\frac{\hbar^{2}}{2m}\,\nabla^{2}+V-Q_{cl}\right)\psi_{cl},\,\,\,\,Q_{cl}=-\frac{\hbar^{2}}{2m}\,\frac{\nabla^{2}R_{cl}}{R_{cl}}.$
(5)

Writing $\psi_{cl}$ in the polar form $R_{cl}{\rm exp}(iS_{cl}/\hbar)$ and
separating the real and imaginary parts, one gets

$\displaystyle\partial S_{cl}/\partial t+\frac{(\nabla S_{cl})^{2}}{2m}+V$
$\displaystyle=$ $\displaystyle 0,$ (6) $\displaystyle\frac{\partial
R_{cl}^{2}}{\partial
t}+\vec{\nabla}\,.\,\left(\,R_{cl}^{2}\,\frac{\vec{\nabla}S_{cl}}{m}\right)$
$\displaystyle=$ $\displaystyle 0.$ (7)

These are precisely the equations for the action and particle distribution of
classical statistical mechanical systems, as we have seen. Hence, eqn.(5) is
the required equation for the classical wave function of such systems.
Although this equation involves $\hbar$, notice that $\hbar$ drops out of the
eqns (6) and (7). Hence, formulated in terms of a complex wave function
satisfying eqn.(5), classical mechanics does not require $\hbar$ to be zero or
small. In semi-classical approximations of quantum mechanics one has to assume
that $\hbar$ is small compared to the classical action, write a power series
expansion of the action $S$ in powers of $\hbar$ and retain only terms of the
order of $\hbar$. Such approximations hold only when the de Broglie wavelength
of the particle is small compared to the region of the particle’s motion. No
such approximations are needed in writing the above equations which are exact.
The complete quenching of the quantum potential $Q_{cl}$ is achieved by a term
of non-quantum mechanical nature in eqn.(5) and $\psi_{cl}$ is a classical
wave function, not a semi-classical approximation of quantum mechanics.

Consider now the equation

$\displaystyle i\,\hbar\,\frac{\partial\psi}{\partial t}$ $\displaystyle=$
$\displaystyle\left(-\frac{\hbar^{2}}{2m}\,\nabla^{2}+V-\lambda
Q\,\right)\,\psi,\,\,\,\,Q=-\frac{\hbar^{2}}{2m}\,\frac{\nabla^{2}R}{R}$ (8)

where $\lambda$ is a dimensionless scalar parameter. It reduces to eqn.(1) for
$\lambda=0$ and to eqn.(5) for $\lambda=1$. Hence, $\lambda$ is the required
parameter in the equation to distinguish between quantum and classical states.

These two limits can be smoothly connected provided one is prepared to admit
the existence of novel physical states characterized by $0<\lambda<1$. Such
states would be neither quantum mechanical nor classical, being intermediate
between them. Hence, we would like to call them ‘mesostates’. Should such
states exist, they would provide the missing connection between the two
ostensibly disconnected worlds of quantum and classical mechanics.

Writing $\psi$ in the polar form, one gets

$\displaystyle\partial S/\partial t+\frac{(\nabla S)^{2}}{2m}+V+(1-\lambda)Q$
$\displaystyle=$ $\displaystyle 0,$ (9) $\displaystyle\frac{\partial
R^{2}}{\partial
t}+\vec{\nabla}\,.\,\left(\,R^{2}\,\frac{\vec{\nabla}S}{m}\right)$
$\displaystyle=$ $\displaystyle 0.$ (10)

Notice that the Schrödinger equation can be derived from eqn.(8) as a limiting
case, but not vice versa. Hence, eqn.(8) is a new interpolating equation that
has to be postulated. Furthermore, notice that the effective quantum potential
in the theory is $(1-\lambda)Q$. Hence, in view of the relation (4),
$\hat{p}(\lambda)=\sqrt{1-\lambda}\hat{p}$, and the commutation relation
between the momentum and position operators is

$\left[\hat{p}(\lambda),q\right]=-i\sqrt{1-\lambda}\hbar,$ (11)

which reduces to the quantum mechanical result in the limit $\lambda=0$. In
the classical limit $\lambda=1$, however, the momentum and position operators
commute without requiring $\hbar=0$.

##  2 Density Matrices

It is essential to use density matrices rather than wave functions in taking
the classical limit. Let us first consider the quantum mechanical limit
$\lambda=0$. Writing

$\displaystyle\psi_{q}$ $\displaystyle=$ $\displaystyle
a\psi_{q1}+b\psi_{q2},\,\,\,\,\,\,a^{2}+b^{2}=1,$ (12)
$\displaystyle\psi_{q1}$ $\displaystyle=$ $\displaystyle
R_{q1}e^{\frac{i}{\hbar}S_{q1}}|u\rangle=R_{q1}e^{\frac{i}{\hbar}S_{q1}}\left(\begin{array}[]{c}1\\\
0\end{array}\right),$ (15) $\displaystyle\psi_{q2}$ $\displaystyle=$
$\displaystyle
R_{q2}e^{\frac{i}{\hbar}S_{q2}}|v\rangle=R_{q2}e^{\frac{i}{\hbar}S_{q2}}\left(\begin{array}[]{c}0\\\
1\end{array}\right),$ (18)

where both $\psi_{q1}$ and $\psi_{q2}$ satisfy the Schrödinger equation, one
gets the density matrix

$\displaystyle\rho_{q}$ $\displaystyle=$ $\displaystyle a^{2}|u\rangle\langle
u|+b^{2}|v\rangle\langle v|+ab\left[|u\rangle\langle
v|e^{\frac{i}{\hbar}(S_{q1}-S_{q2})}+|v\rangle\langle
u|e^{-\frac{i}{\hbar}(S_{q1}-S_{q2})}\right]$ (21) $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}a^{2}&ab\,e^{-i\delta}\\\
ab\,e^{i\delta}&b^{2}\end{array}\right)$

where $\delta=(S_{q2}-S_{q1})/\hbar$. Notice that this matrix is singular and
corresponds to a single wave function $\psi_{q}$.

It is clear from eqn.(9) that a system retains a degree of quantum coherence
in the domain $0\leq\lambda<1$. Hence, in this domain one can write a
superposition of wave functions

$\displaystyle\psi$ $\displaystyle=$ $\displaystyle
a\psi_{1}+b\psi_{2},\,\,\,\,\,\,a^{2}+b^{2}=1,$ (22) $\displaystyle\psi_{1}$
$\displaystyle=$ $\displaystyle R_{1}e^{\frac{i}{\hbar}S_{1}}|u\rangle,$ (23)
$\displaystyle\psi_{2}$ $\displaystyle=$ $\displaystyle
R_{2}e^{\frac{i}{\hbar}S_{2}}|v\rangle$ (24)

where both $\psi_{1}$ and $\psi_{2}$ are solutions of equation (8). The
density matrix is

$\displaystyle\rho^{\lambda}$ $\displaystyle=$ $\displaystyle
a^{2}|u\rangle\langle u|+b^{2}|v\rangle\langle v|+ab\left[|u\rangle\langle
v|e^{-if(\lambda)\delta}+|v\rangle\langle u|e^{if(\lambda)\delta}\right]$ (27)
$\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}a^{2}&ab\,e^{-if(\lambda)\delta}\\\
ab\,e^{if(\lambda)\delta}&b^{2}\end{array}\right),$

where $\delta=(S_{2}-S_{1})/\hbar$, and $f(\lambda)$ is a function that goes
to unity in the limit $\lambda=0$. This can be verified for cases where the
potential $V$ is time independent by using the relation $\partial S/\partial
t=-E$ and introducing a realist ontology through the ‘guidance condition’

$p(\lambda)=\nabla S$ (28)

to write eqn.(9) in the form

$\displaystyle p^{2}(\lambda)$ $\displaystyle=$ $\displaystyle
2m\left[E-(V+Q)+\lambda Q\right]$ $\displaystyle=$ $\displaystyle
2m\left[E-(V+Q)\right]\left[1+\frac{\lambda Q}{E-(V+Q)}\right]$
$\displaystyle\equiv$ $\displaystyle p_{q}^{2}f^{2}(\lambda)$ (30)

where $p_{q}$ is the quantum mechanical momentum in the Bohmian sense, and

$S=\int p(\lambda)dx=\int p_{q}f(\lambda)dx.$ (31)

Clearly, $f(0)=1$. In the classical limit $\lambda=1$, we get

$p^{2}_{cl}=2m\left[E-V\right]$ (32)

which is independent of $Q$, and also $S_{cl}$ is independent of $R_{cl}$, as
we have seen before. Hence, all coherence is lost, and one cannot write a
superposition like (22) in the classical limit. However, one can still write a
density matrix in the diagonal form

$\rho_{cl}=\left(\begin{array}[]{cc}a^{2}&0\\\ 0&b^{2}\end{array}\right)$ (33)

which describes a statistical mixure of the classical states $\psi_{1cl}$ and
$\psi_{2cl}$.

Notice that this diagonal form of the density matrix describes a true mixture
of classical states (described by wave functions) that cannot be obtained from
standard decoherence theory [16, 17, 18] which holds only in the quantum
mechanical limit $\lambda=0$ in which the states $\psi_{1q}$ and $\psi_{2q}$
remain quantum mechanical although their mutual coherence is lost. Thus, the
diagonal form of the density matrix does not by itself imply classicality in
its full sense.

##  3 The Measurement Problem

In any operational theory a system is first prepared in a certain state
$|S\rangle$ and allowed to propagate and then a measurement is made on it to
determine how the state has evolved. In quantum mechanics this state
$|S\rangle$ is made to interact with a macroscopic measuring apparatus
$|A\rangle$, also treated quantum mechanically, and this in general produces
via unitary Schrödinger evolution an entangled state of the system and
measuring device,

$|SA\rangle=\sum_{i,j}c_{ij}|S\rangle_{i}|A\rangle_{j}$ (34)

where the apparatus states $|A\rangle_{j}$ are eigenstates of some observable
in the measurement basis. Its density operator is

$\rho=|SA\rangle\langle SA|$ (35)

which satisfies the condition $\rho^{2}=\rho$, ${\rm Tr}\rho=1$. This contains
off-diagonal interference terms in the presence of which it is not legitimate
to conclude that the states $|A\rangle_{j}$ have definite eigenvalues of the
observable. Hence a second measurement has to be performed on the apparatus
states, leading again to similar conclusions, requiring a third measurement,
and this chain is obviously non-terminating. It has been argued that this
infinite regress eventually culminates in a non-quantum mechanical subjective
perception [19]. von Neumann represented this termination by a non-unitary
projection which produces a reduced density operator

$\hat{\rho}=\sum_{i}|SA\rangle|A\rangle_{ii}\langle A|\langle SA|$ (36)

with the properties $\hat{\rho}^{2}\neq\hat{\rho},\,{\rm Tr}\hat{\rho}=1$,
whose diagonal elements are $|c_{ii}|^{2}$ and whose off-diagonal interference
terms have been deleted [11].

To have an objective interpretation of the measuring process, as some would
prefer [20], it is necessary to truncate von Neumann’s chain immediately after
the first measurement. This can be done if measurement is regarded as a
process in which a micro system interacts with an objective and effectively
classical measuring apparatus with an enormously large number of internal
thermodynamic degrees of freedom which are inevitably excited [22] and act
like a heat bath, and which responds by changing its original metastable state
to a final thermodynamic equilibrium state without substantially affecting the
micro system. After the measurement interaction the wave function of the total
system splits into several non-overlapping branches in the pointer basis, and
the probability of future overlaps among these branches is rendered negligibly
small for all practical purposes (FAPP) due to thermodynamic irreversibility.
This is the precursor of modern decoherence theory.

Neverthless, without a realist ontology in which the micro system (the
‘particle’) enters only one of the branches of the final wave function at a
time, no definite measurement outcome is predicted, and the measurement
problem remains. Bohmian mechanics [23] goes a step further by introducing
precisely this realist ontology, and replacing von Neumann’s projection by the
‘guidance condition’. However, the guidance condition does not lead to
irreversibility, and hence even in the Bohmian interpretation the future
overlaps among the different branches of the final wave function have to be
made highly improbable by invoking thermodynamic arguments [3, 4, 24]. Hence,
only pragmatic (FAPP) solutions to the measurement problem are possible within
the objective approach, not a fundamental one.

As is well known, Bohr emphasized the fundamental role of classical concepts
and classical measuring devices [25]. Though there is growing experimental
evidence in support of superpositions of macroscopically distinct states which
have no classical counterparts [26], Bohr’s position is not negated by them
because such states cannot obviously be used as measuring devices for the
reasons stated above. The fact of the matter is that there is overwhelming
empirical evidence that macroscopically distinct classical states do exist to
produce definite outcomes of measurements. It is therefore of paramount
importance to explore how the established quantum and classical worlds can be
mathematically connected in a fundamental way without having to invoke either
subjective interventions or pragmatic thermodynamic arguments. This is what is
attempted in this paper.

##  4 Entanglement

Let us for simplicity consider a two-particle system described by the equation

$\displaystyle
i\,\hbar\,\frac{\partial\psi(\vec{x}_{1},\vec{x}_{2},t)}{\partial t}$
$\displaystyle=$
$\displaystyle\left(-\frac{\hbar^{2}}{2m_{1}}\,\nabla_{1}^{2}-\frac{\hbar^{2}}{2m_{2}}\,\nabla_{2}^{2}+V(\vec{x}_{1},\vec{x}_{2})-\lambda_{1}Q_{1}-\lambda_{2}Q_{2}\right)\psi(\vec{x}_{1},\vec{x}_{2},t),$
(37) $\displaystyle Q_{1}$ $\displaystyle=$
$\displaystyle-\frac{\hbar^{2}}{2m_{1}}\frac{\nabla_{1}^{2}R}{R},\,\,\,\,Q_{2}=-\frac{\hbar^{2}}{2m_{2}}\frac{\nabla_{2}^{2}R}{R},$
(38)

with $0\leq\lambda_{1,2}\leq 1$. Writing

$\psi(\vec{x}_{1},\vec{x}_{2},t)=R(\vec{x}_{1},\vec{x}_{2},t){\rm
exp}\left[\frac{i}{\hbar}S(\vec{x}_{1},\vec{x}_{2},t)\right].$ (39)

substituting this in (37) and separating the real and imaginary parts, we get

$\displaystyle\partial S/\partial
t+\frac{(\nabla_{1}S)^{2}}{2m_{1}}+\frac{(\nabla_{2}S)^{2}}{2m_{2}}+V(\vec{x}_{1},\vec{x}_{2})+(1-\lambda_{1})Q_{1}+(1-\lambda_{2})Q_{2}=0,$
(40) $\displaystyle\frac{\partial R^{2}}{\partial
t}+{\bf\nabla}_{1}\,.\,\left(\,R^{2}\,\frac{{\bf\nabla}_{1}\,S}{m_{1}}\right)+{\bf\nabla}_{2}\,.\,\left(\,R^{2}\,\frac{{\bf\nabla}_{2}\,S}{m_{2}}\right)=0.$
(41)

Now, for simplicity, consider an entangled pair of qubit systems

$\psi(\vec{x}_{1},\vec{x}_{2},t)=a\psi_{1+}(\vec{x}_{1},t)\psi_{2-}(\vec{x}_{2},t)+b\psi_{1-}(\vec{x}_{1},t)\psi_{2+}(\vec{x}_{2},t),\,\,\,\,a^{2}+b^{2}=1,$
(42)

where $\pm$ denote the two orthogonal components of each system. Writing

$\displaystyle\psi_{i\pm}(\vec{x}_{i},t)$ $\displaystyle=$ $\displaystyle
R_{i\pm}(\vec{x}_{i},t)|u_{i\pm}\rangle{\rm
exp}\left[\frac{i}{\hbar}S_{i\pm}(\vec{x}_{i},t)\right],\,\,\,\,i=1,2,$
$\displaystyle u_{i+}$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{c}1\\\
0\end{array}\right),\,\,\,\,u_{i-}=\left(\begin{array}[]{c}0\\\
1\end{array}\right),$ (47)

we get

$\displaystyle R^{2}(\vec{x}_{1},\vec{x}_{2},t)$ $\displaystyle=$
$\displaystyle|a|^{2}R_{1+}^{2}R_{2-}^{2}+|b|^{2}R_{1-}^{2}R_{2+}^{2}+2abR_{1+}R_{1-}R_{2+}R_{2-}{\rm
cos}\left[\delta_{1}+\delta_{2}\right],$ $\displaystyle\delta_{1}$
$\displaystyle=$
$\displaystyle\frac{1}{\hbar}\left(S_{1+}-S_{1-}\right),\,\,\,\,\delta_{2}=\frac{1}{\hbar}\left(S_{2+}-S_{2-}\right)$
(48)

and

$\displaystyle S(\vec{x}_{1},\vec{x}_{2},t)=\hbar\,{\rm arctan}\theta$
$\displaystyle\theta=\frac{aR_{1+}R_{2-}{\rm
sin}(\frac{1}{\hbar}(S_{1+}+S_{2-}))+bR_{1-}R_{2+}{\rm
sin}(\frac{1}{\hbar}(S_{1-}+S_{2+}))}{aR_{1+}R_{2-}{\rm
cos}(\frac{1}{\hbar}(S_{1+}+S_{2-}))+bR_{1-}R_{2+}{\rm
cos}(\frac{1}{\hbar}(S_{1-}+S_{2+}))}.$ (49)

The density matrix corresponding to the wave function (42) is given by

$\displaystyle\rho$ $\displaystyle=$
$\displaystyle\left[a^{2}|u_{1+}\rangle\langle
u_{1+}|+b^{2}|u_{1=}\rangle\langle
u_{1-}|\right]\otimes\left[b^{2}|u_{2+}\rangle\langle
u_{2+}|+a^{2}|u_{2-}\rangle\langle u_{2-}|\right]$ (54) $\displaystyle+$
$\displaystyle\left[ab|u_{1+}\rangle\langle
u_{1-}|e^{i\delta_{1}}+ab|u_{1-}\rangle\langle
u_{1+}|e^{-i\delta_{1}}\right]\otimes\left[ab|u_{2+}\rangle\langle
u_{2-}|e^{i\delta_{2}}+ab|u_{2-}\rangle\langle u_{2+}|e^{-i\delta_{2}}\right]$
$\displaystyle=$ $\displaystyle\left(\begin{array}[]{cc}a^{2}&0\\\
0&b^{2}\end{array}\right)_{1}\otimes\left(\begin{array}[]{cc}b^{2}&0\\\
0&a^{2}\end{array}\right)_{2}$ $\displaystyle+$
$\displaystyle\left(\begin{array}[]{cc}0&ab\,e^{if_{1}(\lambda_{1})\delta_{1}}\\\
ab\,e^{-f_{1}(\lambda_{1})i\delta_{1}}&0\end{array}\right)_{1}\otimes\left(\begin{array}[]{cc}0&ab\,e^{if_{2}(\lambda_{2})\delta_{2}}\\\
ab\,e^{-if_{2}(\lambda_{2})\delta_{2}}&0\end{array}\right)_{2},$ (59)

where $f_{1,2}(\lambda_{1,2})$ are defined analogous to eqn.(30).

Now, let system 1 be quantum mechanical ($\lambda_{1}=0$) and system 2 be a
classical apparatus ($\lambda_{2}=1$). Then there is no observable phase
relation between the two apparatus states which are therefore incoherent, and
the density matrix is given by

$\hat{\rho}=\left(\begin{array}[]{cc}a^{2}&0\\\
0&b^{2}\end{array}\right)_{1}\otimes\left(\begin{array}[]{cc}b^{2}&0\\\
0&a^{2}\end{array}\right)_{2}+\left(\begin{array}[]{cc}0&ab\,e^{i\delta_{1}}\\\
ab\,e^{-i\delta_{1}}&0\end{array}\right)_{1}\otimes\left(\begin{array}[]{cc}0&0\\\
0&0\end{array}\right)_{2}$ (60)

which indicates a completely mixed state in spite of system 1 remaining
coherent and quantum mechanical. Note that without a wave function description
of the classical apparatus states, one could not have derived this result.

##  5 An Example of Measurement

Let us take the case of an observation designed to measure some observable
$\mathcal{Q}$ of a particle with wave function $\psi_{1}(\vec{x},t)$. Let the
wave function of the apparatus be $\psi_{2}(y,t)$ where $y$ is the relevant
coordinate of the apparatus. The interaction Hamiltonian is taken to be

$H_{I}=-g\mathcal{Q}p_{y}$ (61)

where $g$ is a suitable coupling parameter and $p_{y}$ is the momentum
corresponding to $y$. During the impulsive interaction the free evolution of
the two systems can be ignored, and

$\displaystyle i\hbar\frac{\partial\Psi}{\partial t}$ $\displaystyle=$
$\displaystyle-g\mathcal{Q}p_{y}\Psi=\left(\frac{ig}{\hbar}\right)\mathcal{Q}\frac{\partial\Psi}{\partial
y}$ (62)

is a good approximation, and where, under the assumption of discrete
eigenfunctions,

$\displaystyle\Psi(\vec{x},y,t)$ $\displaystyle=$
$\displaystyle\sum_{q}\psi_{1q}(\vec{x})\psi_{2q}(y,t),$ (63)
$\displaystyle\mathcal{Q}\psi_{1q}(\vec{x})$ $\displaystyle=$ $\displaystyle
q\psi_{1q}(\vec{x}).$ (64)

Initially the electron and the apparatus are independent, and hence

$\Psi(\vec{x},y)=\psi_{10}(\vec{x})\psi_{20}(y)=\psi_{20}(y)\sum_{q}c_{q}\psi_{1q}(\vec{x}).$
(65)

The final wave function is given by

$\Psi(\vec{x},y,t)=\sum_{q}c_{q}\psi_{1q}(\vec{x})\psi_{20}(y-gqt/\hbar^{2}).$
(66)

which is an entangled wave function embodying a correlation between the
eigenvalue $q$ of $\mathcal{Q}$ and the apparatus coordinate $y$. Writing

$\Psi(\vec{x},y,t)=R(\vec{x},y,t){\rm
exp}\left[\frac{i}{\hbar}S(\vec{x},y,t)\right],$ (67)

we get

$\displaystyle\partial S/\partial
t+\frac{(\nabla_{x}S)^{2}}{2m_{1}}+\frac{(\partial_{y}S)^{2}}{2m_{2}}+(1-\lambda_{1})Q_{1}+(1-\lambda_{2})Q_{2}=0,$
(68) $\displaystyle
Q_{1}=-\frac{\hbar^{2}}{2m_{1}}\frac{\nabla_{x}^{2}R}{R},\,\,\,\,Q_{2}=-\frac{\hbar^{2}}{2m_{2}}\frac{\partial_{y}^{2}R}{R},$
(69) $\displaystyle\frac{\partial R^{2}}{\partial
t}+{\bf\nabla}_{x}\,.\,\left(\,R^{2}\,\frac{{\bf\nabla}_{x}\,S}{m_{1}}\right)+\partial_{y}\left(\,R^{2}\,\frac{\partial_{y}S}{m_{2}}\right)=0.$
(70)

If the particle is quantum mechanical ($\lambda_{1}=0$), eqn. (68) must be
replaced by

$\partial S/\partial
t+\frac{(\nabla_{x}S)^{2}}{2m_{1}}+\frac{(\partial_{y}S)^{2}}{2m_{2}}+Q_{1}+(1-\lambda_{2})Q_{2}=0.$
(71)

Using the guidance condition, one can write the velocities as

$\displaystyle\frac{d\vec{x}_{1}}{dt}$ $\displaystyle=$
$\displaystyle\frac{1}{m_{1}}\vec{\nabla}_{x}S(\vec{x},y,t),$ (72)
$\displaystyle\frac{dy}{dt}$ $\displaystyle=$
$\displaystyle\frac{1}{m_{2}}\partial_{y}S(\vec{x},y,t),$ (73)

and the second order equations of motion are

$\displaystyle\frac{d\vec{p}_{1}}{dt}$ $\displaystyle=$
$\displaystyle-\vec{\nabla}_{x}Q_{1},$ (74) $\displaystyle\frac{dp_{y}}{dt}$
$\displaystyle=$ $\displaystyle-\partial_{y}(1-\lambda_{2})Q_{2}.$ (75)

A specific example would be spin measurement with $\mathcal{Q}=\sigma_{z}$. In
this case the apparatus is a dipole magnetic field in the $xz$ plane with a
gradient in the $z$-direction, and let

$\displaystyle\psi_{1}(x,z)$ $\displaystyle=$
$\displaystyle\left(c_{+}|u_{+}\rangle+c_{-}|u_{-}\rangle\right)f(z)e^{ikx},$
(76) $\displaystyle\sigma_{z}|u_{\pm}\rangle$ $\displaystyle=$
$\displaystyle\pm|u_{\pm}\rangle$ (77)

be the wave function of a spin-$\frac{1}{2}$ particle travelling in the
$x$-direction and passing through the magnet at $t=0$, $f(z)$ being a Gaussian
wave packet and $c_{\pm}$ the probability amplitudes for the spin-$\uparrow$
and spin-$\downarrow$ states satisfying the condition $c_{+}^{2}+c_{-}^{2}=1$.
Then the initial wave function is

$\Psi(x,z)=\psi_{20}(z)\psi_{1}(x,z),$ (78)

and the interaction Hamiltonian is

$H_{I}=i\hbar\mu_{B}\frac{\partial B}{\partial z}.$ (79)

As a result of the impulsive action of the magnetic field, two wave packets
are created which begin to separate in the $z$ direction, and after some time
$t$ the wave function has the form

$\Psi(x,z,t)=\left[c_{+}f_{+}(x,z,t)|u_{+}\rangle\psi_{20}(z_{+})+c_{-}f_{-}(x,z,t)|u_{-}\rangle\psi_{20}(z_{-})\right],$
(80)

where $f_{\pm}(x,z,t)$ are the evolved wave packets [27] and $z_{\pm}$ are the
corresponding shifted coordinates of the apparatus. This is an entangled
state, though the particle is in one of these wave packets only. Now, if the
apparatus states are classical ($\lambda_{2}=1$), their relative phases are
not observable and they are incoherent. Consequently, the density matrix is
given by

$\displaystyle\rho$ $\displaystyle=$
$\displaystyle\left(\begin{array}[]{cc}c_{+}^{2}&0\\\
0&0\end{array}\right)_{1}\otimes\left(\begin{array}[]{cc}1&0\\\
0&0\end{array}\right)_{2}+\left(\begin{array}[]{cc}0&0\\\
0&c_{-}^{2}\end{array}\right)_{1}\otimes\left(\begin{array}[]{cc}0&0\\\
0&1\end{array}\right)_{2}+\left(\begin{array}[]{cc}0&c_{+}c_{-}\,e^{i\delta_{1}}\\\
0&0\end{array}\right)_{1}\otimes\left(\begin{array}[]{cc}0&0\\\
0&0\end{array}\right)_{2}$ (93) $\displaystyle+$
$\displaystyle\left(\begin{array}[]{cc}0&0\\\
c_{+}c_{-}\,e^{-i\delta_{1}}&0\end{array}\right)_{1}\otimes\left(\begin{array}[]{cc}0&0\\\
0&0\end{array}\right)_{2}$ (98)

where $\delta_{1}$ is the phase difference between the two spin states. It is
diagonal and shows that after the measurement interaction the system is a
statistical mixture of two wave functions
$f_{+}(x,z,t)|u_{+}\rangle\psi_{20}(z_{+})$ and
$f_{-}(x,z,t)|u_{-}\rangle\psi_{20}(z_{-})$ with the particle in only one of
them, resulting in the prediction of definite measurement outcomes with
probabilities $c^{2}_{+}$ and $c^{2}_{-}$ respectively without collapse, i.e.
without one of these wave functions having to vanish every time a definite
outcome occurs. The diagonal form of the density matrix is due to the fact
that the two apparatus states $\psi_{20}(z_{+})$ and $\psi_{20}(z_{-})$ are
incoherent, i.e. have no observable phase relation.

The origin of the debate on nonlocality in quantum mechanics can be traced
back to Einstein’s observations at the 1927 Solvay Conference. Consider the
case of an ontic wavefunction $\psi$ describing a single particle [21]. After
passing through a small hole in a screen, the wave function of the particle
spreads out on the other side of it in the form of a spherical wave, and is
finally detected by a large hemispherical detector. The wave function
propagating towards the detector does not show any privileged direction.
Einstein observes:

> If $|\psi|^{2}$ were simply regarded as the probability that at a certain
> point a given particle is found at a given time, it could happen that the
> same elementary process produces an action in two or several places on the
> screen. But the interpretation, according to which the $|\psi|^{2}$
> expresses the probability that this particle is found at a given point,
> assumes an entirely peculiar mechanism of action at a distance, which
> prevents the wave continuously distributed in space from producing an action
> in two places on the screen.

Einstein later remarks that this ‘entirely peculiar mechanism of action at a
distance’ is in contradiction with the postulate of relativity. Hence, the
joint assumption of reality of the wave function and locality is incompatible
with the Schrödinger equation together with the Born rule. We must point out
that the nonlocality pointed out by Einstein in this example is clearly a
consequence of implicitly assuming a ‘projective measurement’ by the detector,
and hence can be eliminated by first considering the detector to be in a
‘meso’ state and then going to the classical limit, as explained above.

##  6 The Case of EPR Entanglement

Consider the EPR-Bohm wave function to have the initial form

$\psi_{1}(z_{a}^{\prime},z_{b})=f_{a}(z_{a}^{\prime})f_{b}(z_{b})\frac{1}{\sqrt{2}}\left[|u^{a}_{+}\rangle|v^{b}_{-}\rangle-|u^{a}_{-}\rangle|v^{b}_{+}\rangle\right]$
(99)

where $f_{a}(z_{a}^{\prime})$ and $f_{b}(z_{b})$ are Gaussian wave packets,
$z_{a}^{\prime}$ and $z_{b}$ are coordinates of two particles $a$ and $b$ in
the $z^{\prime}$ and $z$ directions respectively, and
$\sigma^{a}_{z}|u^{a}_{\pm}\rangle=\pm|u^{a}_{\pm}\rangle$,
$\sigma^{b}_{z}|v^{b}_{\pm}\rangle=\pm|v^{b}_{\pm}\rangle$ [28]. Denoting the
initial state of the measuring apparatus by

$\psi_{20}(z^{\prime}_{A},z_{B})=\psi_{A}(z^{\prime}_{A})\psi_{B}(z_{B})$
(100)

where $\psi_{A}(z^{\prime}_{A})$ and $\psi_{B}(z_{B})$ are the apparatus wave
functions used by Alice and Bob respectively, the wave function of the initial
state is

$\Psi(z_{a}^{\prime},z_{b},z_{A}^{\prime},z_{B})=\psi_{1}(z_{a}^{\prime},z_{b})\psi_{20}(z^{\prime}_{A},z_{B}).$
(101)

Therefore, the entangled state at time $t$ after the impulsive measurement
interaction is

$\displaystyle\Psi(z_{a}^{\prime},z_{b},z_{A}^{\prime},z_{B},t)$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}f_{a}(z_{a}^{\prime},t)f_{b}(z_{b},t)\left[|u^{a}_{+}\rangle|v^{b}_{-}\rangle\psi_{A}(z^{\prime}_{A+})\psi_{B}(z_{B-})\right]$
(102) $\displaystyle-$
$\displaystyle\frac{1}{\sqrt{2}}f_{a}(z_{a}^{\prime},t)f_{b}(z_{b},t)\left[|u^{a}_{-}\rangle|v^{b}_{+}\rangle\psi_{A}(z^{\prime}_{A-})\psi_{B}(z_{B+})\right]$

where the notation follows that of the previous section with obvious
generalizations. The density operator is

$\displaystyle\rho$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left[|u^{a}_{+}\rangle\langle
u^{a}_{+}||v^{b}_{-}\rangle\langle v^{b}_{-}||u^{A}_{+}\rangle\langle
u^{A}_{+}||v^{B}_{-}\rangle\langle v^{B}_{-}|+|u^{a}_{-}\rangle\langle
u^{a}_{-}||v^{b}_{+}\rangle\langle v^{b}_{+}||u^{A}_{-}\rangle\langle
u^{A}_{-}||v^{B}_{+}\rangle\langle v^{B}_{+}|\right]$ (103) $\displaystyle-$
$\displaystyle\frac{1}{2}\left[e^{i\delta_{ab}}|u^{a}_{+}\rangle\langle
u^{a}_{-}||v^{b}_{-}\rangle\langle
v^{b}_{+}|e^{i\delta_{AB}}|u^{A}_{+}\rangle\langle
u^{A}_{-}||v^{B}_{-}\rangle\langle v^{B}_{+}|\right]$ $\displaystyle-$
$\displaystyle\frac{1}{2}\left[e^{-i\delta_{ab}}|u^{a}_{-}\rangle\langle
u^{a}_{+}||v^{b}_{+}\rangle\langle
v^{b}_{-}|e^{-i\delta_{AB}}|u^{A}_{-}\rangle\langle
u^{A}_{+}||v^{B}_{+}\rangle\langle v^{B}_{-}|\right],$

where

$\displaystyle\delta_{ab}$ $\displaystyle=$
$\displaystyle(\delta_{a+}-\delta_{a-})+(\delta_{b-}-\delta_{b+}),$ (104)
$\displaystyle\delta_{AB}$ $\displaystyle=$
$\displaystyle(\delta_{A+}-\delta_{A-})+(\delta_{B-}-\delta_{B+}).$ (105)

In the realist (Bohmian) interpretation the particles $a$ and $b$ are always
in one of their two possible states determined by the wave functions (102),
resulting in definite outcomes.

Now, if the apparatus states are classical, they are incoherent and the
density matrix is diagonal:

$\displaystyle\hat{\rho}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left[|u^{a}_{+}\rangle\langle
u^{a}_{+}||v^{b}_{-}\rangle\langle v^{b}_{-}||u^{A}_{+}\rangle\langle
u^{A}_{+}||v^{B}_{-}\rangle\langle v^{B}_{-}|+|u^{a}_{-}\rangle\langle
u^{a}_{-}||v^{b}_{+}\rangle\langle v^{b}_{+}||u^{A}_{-}\rangle\langle
u^{A}_{-}||v^{B}_{+}\rangle\langle v^{B}_{+}|\right].$ (106)

This does not, however, imply that the EPR-Bohm state collapses into one of
the two wave functions in (102) every time a definite outcome occurs. The
diagonal form is only indicative of the fact that the relative phases between
the classical apparatus states are not observable. Hence, there being no
collapse, there is no measurement induced nonlocality in this theory.

It must be emphasized that the nonlocality inherent in the quantum potential
$Q$ is not connected with ‘measurement’ as such, and that it occurs in multi-
dimensional configuration spaces. The EPR paradox is resolved in realist
theories of this kind, such as Bohmian mechanics, by showing that the nonlocal
and spin-dependent quantum potential associated with the total quantum state
rotates the spin vectors of the two particles in such a manner as always to
preserve the correlations implied by the quantum state [27, 28].

##  7 Significance of $\lambda$

So far $\lambda$ has played the role of a mathematical parameter which
characterizes the various modes in which matter can exist, namely quantum
mechanical ($\lambda=0$), classical ($\lambda=1$) and perhaps also
‘mesostates’ ($0<\lambda<1$), and provides a smooth link between them.
However, its physical significance needs to be clarified. It could also be
that $\lambda$ is the unit step function, and no mesostates exist. That would
rule out smooth quantum-classical transitions.

Since $0\leq\lambda\leq 1$, it can be interpreted as a probabilistic measure
of the ‘classicality’ of a state, $\lambda=1$ being $100\%$ classical and
$\lambda=0$ being $0\%$ classical. Mesostates would presumably be multi-
particle states with varying degrees of ‘classicality’, depending on the
number of constituents, their internal structure, temperature, etc., i.e. with
varying degrees of the presence of the quantum potential which encapsulates
quantum coherence. The quantum-classical transition is therefore a
‘decoherence’ process in which the quantum potential is gradually quenched. It
is therefore different from standard environment-induced decoherence which
occurs within quantum mechanics. Hence, $\lambda$ is also a probabilistic
measure of decoherence, the maximum occuring for fully classical states with
$\lambda=1$.

The probabilistic nature of $\lambda$ indicates an underlying stochastic
process. Now, the cumulative distribution functions (CDFs) for many common
probability distribution functions are sigmoidal. For example, the CDF of a
normal distribution,

$F(x)=\int_{-\infty}^{x}\frac{e^{-t^{2}/2}}{\sqrt{2\pi}},$ (107)

is a sigmoid which is the probability that the random variable $t$ takes on a
value less than or equal to $x$. Hence, modelling the underlying stochastic
process by a single random variable, one can interpret $\lambda$ as the CDF of
its probability density function. However, since the integral (107) does not
exist in a simple closed form and is usually computed numerically, for
illustrative purposes one can use the logistic function

$\lambda=\frac{1}{1+e^{-b(t-t_{0})}}$ (108)

which is qualitatively similar in form, and where $b$ is a measure of the
steepness of the sigmoid and $t_{0}$ is the $t$-value of the sigmoid’s
midpoint. It reduces to the $\theta$ function in the limit
$b\rightarrow\infty$. Hence

$1-\lambda=\frac{1}{1+e^{b(t-t_{0})}}$ (109)

is the complementary CDF to the logistic function, and it is this function
that occurs in eqns.(9).

In general, the underlying stochastic process may involve multiple random
variables, and hence one must use the joint probability density function or
the joint probability mass function depending on whether the random variables
are all continuous or discrete.

##  8 Particle in a Box

Let us now consider the problem of a particle in a box which has acquired
immense practical importance as a theoretical tool to study quantum dots. As
is well known, the solution of the time independent Schrödinger equation

$-\frac{\hbar^{2}}{2m}\frac{d^{2}\psi_{q}}{dx^{2}}=E\psi_{q}$ (110)

for a particle inside a one-dimensional box of length $L$ is

$\psi_{qn}=\sqrt{\frac{2}{L}}{\rm
sin}k_{n}x,\,\,\,\,k_{n}=\frac{n\pi}{L},\,\,n=1,2,3,\cdots$ (111)

and the quantized energies are given by

$E_{n}=\frac{n^{2}\pi^{2}\hbar^{2}}{2mL^{2}}.$ (112)

It will be instructive to see how this result can be derived in Bohmian
mechanics. The starting point will be eqn.(2) with $V=0,\,\lambda=0$ for every
wave function $\psi_{qn}$, namely

$p^{2}_{n}(0)=2m\left[E_{n}-Q_{n}\right].$ (113)

One can now calculate the quantum potentials

$Q_{n}=-\frac{\hbar^{2}}{2m}\frac{|\psi_{qn}|^{\prime\prime}}{|\psi_{qn}|}=\frac{\hbar^{2}k_{n}^{2}}{2m}=\frac{n^{2}\pi^{2}\hbar^{2}}{2mL^{2}}$
(114)

where ′ denotes the derivative w.r.t $x$, and notice that the quantum
mechanical result (112) follows provided $p_{n}(0)=0$, which shows that a
quantum mechanical particle in a box is at rest, and that the quantized
energies are simply the quantum potentials.

Let us now see what the time independent version of eqn.(8), namely

$-\frac{\hbar^{2}}{2m}\frac{d^{2}\psi}{dx^{2}}=(E+\lambda Q)\psi$ (115)

has to say about the particle in a box. Our starting point will be eqn.(2)
with $V=0$ for every $n$, i.e.

$\displaystyle p_{n}^{2}(\lambda)$ $\displaystyle=$ $\displaystyle
2m\left[E_{n\lambda}-(1-\lambda)Q_{n}\right],$ (116)

which reduces to the quantum mechanical result for $E_{n}$ in the limit
$\lambda=0$ provided $p_{n}(0)=0$. If $0<\lambda<1$, we have

$E_{n\lambda}=(1-\lambda)Q_{n}=(1-\lambda)\frac{n^{2}\pi^{2}\hbar^{2}}{2mL^{2}}=(1-\lambda)E_{n}$
(117)

if one sets $p_{n}(\lambda)=0$ to avoid quantized momenta. However, in the
classical limit $\lambda=1$, the quantum potentials get cancelled, and one has

$E=\frac{p^{2}_{cl}}{2m},$ (118)

and there is no quantization and no restriction on the particle to be at rest.

##  9 Possible Experimental Test

Electrons in low-dimensional nanostructures like quantum dots, wires and wells
exhibit quantized energy levels that do not exist in the bulk materials.
Structures that are intermediate between the bulk materials and the extreme
nano clusters provide a possible testing ground for the smooth quantum-
classical transitions implied by eqn.(8). For example, the result (117) for a
particle in a box implies that as a 3D box is flattened, the quantized energy
levels of the particle begin to emerge and attain the full quantum mechanical
values in the limit $\lambda=0$. Conversely, in the bottom-up approach the
energy levels should start to disappear. The spacings between the energy
levels should change according to the relation

$\frac{\Delta E_{\lambda}}{\Delta
E}=\frac{E_{(n+1)\lambda}-E_{n\lambda}}{E_{(n+1)}-E_{n}}=(1-\lambda).$ (119)

Hence, there is a departure from the pure quantum mechanical prediction.
Empirical studies of the changing energy levels as a quantum dot is formed in
the bottom-up or top-down method can therefore help test the basic tenet of
the theory and also determine the nature of variation of the $\lambda$
parameter by comparisons with predictions based on models such as eqn.(109).
In practice, nanostructures contain more than just a single particle, and
hence inter-particle effects need to be taken into account.

##  10 Summary

The basic idea on which the paper has been developed is that empirical
evidence strongly suggests the existence of two apparently disparate domains
of nature, one macroscopic and classical and the other microscopic and quantum
mechanical, with no clear connection between the two. Hence there is a need
for some new physics to connect these domains. The fundamental problem with
quantum mechanics is its inability to predict definite outcomes of
measurements which can only be done with macroscopic classical measuring
devices, but there is no scale or parameter in the theory to distinguish
between microscopic and macroscopic objects. It is precisely this shortcoming
of quantum mechanics that can be overcome by postulating a new equation (5)
with a scalar parameter $0\leq\lambda\leq 1$ such that quantum mechanics is
recovered in the limit $\lambda=0$ and classical mechanics in the limit
$\lambda=1$. The domain $0<\lambda<1$ describes a new form of matter that is
predicted by the theory and is neither classical nor quantum mechanical, being
intermediate between them and hence may be called ‘meso’. The parameter
$\lambda$ is a probabilistic measure of the ‘classicality’ of a state. Given a
real ontology, this theory predicts definite outcomes of measurements with
classical measuring devices, without requiring any collapse and collapse-
induced nonlocality.

The theory is testable in principle with nanostructures like the so called
quantum dots, quantum wires and quantum wells which are ‘mesostates’ according
to this theory. Further work is in progress to elaborate on such tests, as
well as in extending the theory to electrodynamics, specially to polarization
optics.

##  11 Acknowledgement

The author acknowledges a grant from the National Academy of Sciences, India
which enabled this work to be undertaken.

## References

  * [1] J. S. Bell, ‘Against Measurement’ in Speakable and Unspeakable in Quantum Mechanics, Cambridge University Press, Cambridge, Second Edn. (2004).
  * [2] H. Everett, Rev. Mod. Phys. 29, 454-462 (1957); see also B. De Witt and N. Graham (eds.), The Many-Worlds Interpretation of Quantum Mechanics, Princeton NJ: Princeton University Press, 1973.
  * [3] D. Bohm, Phys. Rev. 85, 166-79 (1952).
  * [4] D. Bohm, Phys. Rev. 85, 180-93 (1952).
  * [5] G. C. Ghirardi, A. Rimini and T. Weber, Phys. Rev. D 34, 470 (1985).
  * [6] M. Schlosshauer, J. Kofler and A. Zeilinger, ‘A Snapshot of Foundational Attitudes Toward Quantum Mechanics’, Stud. Hist. Phil. Mod. Phys. 44, 222-230 (2013).
  * [7] A. Einstein, B. Podolsky and N. Rosen, Phys. Rev. 47, 777-80 (1035).
  * [8] For a review see, for example, M. S. Leifer, Quanta 3, 67-155 (2014) and references therein; arxiv: 1409.1570.
  * [9] C. A. Fuchs, N. D. Mermin and R. Schack, An Introduction to QBism, arxiv:1311.5253.
  * [10] B. O. Koopman, Proc. Natl. Acad. Sci. U.S.A. 17, 315 (1931).
  * [11] J. von Neumann, Ann. Math. 33, 587 (1932); ibid. 33, 789-791 (1932).
  * [12] F. Wilczek, Notes on Koopman von Neumann Mechanics, and A Step Beyond, http://frankwilczek.com/2015/koopmanVonNeumann02.pdf, Sep 21, 2015.
  * [13] P. Ghose, Found. of Phys. 32, 871-892 (2002).
  * [14] P. Ghose and M. K. Samal, Found. of Phys. 32, 893-906 (2002).
  * [15] A. Matzkin and V. Nurock, ‘Classical and Bohmian trajectories in semiclassical systems: Mismatch in dynamics, mismatch in reality?’, Studies In History and Philosophy of Science B 39, 17 (2008).
  * [16] R. Omnés, Rev. Mod. Phys. 64, 339 (1990).
  * [17] E. Joos et al., Decoherence and the Appearance of a Classical World in Quantum Theory (2nd ed.), Berlin: Springer, (2003).
  * [18] W. H. Zurek, “Decoherence and the transition from quantum to classical — REVISITED”, arXiv:quant-ph/0306072 (2003). (An updated version of PHYSICS TODAY, 44:36-44 (1991) article)
  * [19] J. von Neuman, Mathematical Foundations of Quantum Mechanics, translation into English by R. T. Beyer, Princeton University Press, Princeton (1955), pp. 347-445.
  * [20] A. Daneri, A. Loinger and G. M. Prosperi, Nucl. Phys. 33, 297-319 (1962).
  * [21] G. Bacciagaluppi, A. Valentini: Quantum Theory at the Crossroads: Reconsidering the 1927 Solvay Conference, pp. 485-487, Cambridge Univ. Press, Cambridge (2009); arXiv: quant-ph/0609184.
  * [22] J. A. Wheeler and W. H. Zurek eds, Quantum Theory and Measurement, Princeton University, Princeton (1983), Section V.
  * [23] See Ref. [3], Section 7 and [4], Section 2.
  * [24] D. Dürr, S. Goldstein, and N. Zanghi, Jour. Stat. Phys., 67(5), 843-907 (1992).
  * [25] N. Bohr in Atomic Theory and the Description of Nature, Cambridge: Cambridge University Press, 1934.
  * [26] J. R. Friedman, V. Patel, W. Chen, S. K. Tolpygo & J. E. Lukens, Nature 406, 43-46 (6 July 2000) — doi:10.1038/35017505.
  * [27] C. Dewdney, P. R. Holland and A. Kypriadinis, Phys. Lett A 119, 259-267 (1986).
  * [28] C. Dewdney, P. R. Holland, A. Kypriadinis and J. P. Vigier, Nature 336, 536-544 (1988).


remarkRemark hypothesisHypothesis claimClaim The Essential Algorithms for the
Matrix ChainF. López, L. Karlsson, and P. Bientinesi [][nocite]ex_supplement

# The Essential Algorithms for the Matrix Chain††thanks: Submitted to the
editors DATE.

Francisco López Department of Computing Science, Umeå Universitet, Sweden (, ,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Lars
Karlsson22footnotemark: 2 Paolo Bientinesi22footnotemark: 2

###### Abstract

For a given product of $n$ matrices, the matrix chain multiplication problem
asks for a parenthesisation that minimises the number of arithmetic
operations. In 1973, Godbole presented a now classical dynamic programming
formulation with cubic time complexity on the length of the chain. The best
known algorithms run in linearithmic time, and the best known approximation
algorithms run in linear time with an approximation factor smaller than two.
All solutions have in common that they select an optimal parenthesisation from
a set of $C_{n-1}$ (Catalan number $n-1$) distinct parenthesisations. We
studied the set of parenthesisations and discovered (a) that all of the
exponentially many parenthesisations are useful in the sense that they are
optimal in an infinite subset of the input space, (b) that only $n+1$
parenthesisations are essential in the sense that they are arbitrarily better
than the second best on an infinite subset of the input space, and (c) that
the best essential parenthesisation is never more than twice as costly as the
best non-essential parenthesisation. Through random sampling of the input
space, we further discovered that the set of essential parenthesisations
includes an optimal parenthesisation in the vast majority of inputs, and that
the best essential parenthesisation is on average much closer to optimal than
the worst-case bound. The results have direct consequences for the development
of compilers for linear algebra expressions where the matrix sizes are unknown
at compile-time.

###### keywords:

matrix multiplication, matrix chain, approximation algorithm, linear algebra
compilers

68N20, 68Q25, 68W25

##  1 Introduction

The classical _matrix chain multiplication problem_ seeks the cheapest way to
multiply a sequence of $n\geq 3$ matrices

(1) $M:=M_{1}M_{2}\cdots M_{n}.$

Since matrix multiplication is associative, the $n-1$ multiplications in (1)
can be performed in any order. There are $(n-1)!$ orderings, some of which are
equivalent in the sense that they perform the same exact set of
multiplications but in different sequential orders. For example,
$(M_{1}M_{2})(M_{3}M_{4})$ has two equivalent orderings, since the
multiplications $M_{1}\times M_{2}$ and $M_{3}\times M_{4}$ are independent.
Each class of equivalent orderings is identified by a specific
_parenthesisation_ of (1). In what follows, we use the term _ordering_ to
refer to the _partial_ ordering of the multiplications imposed by a
parenthesisation. The ordering affects the arithmetic cost (and hence the
execution time) of the evaluation of the matrix chain. Thus, the matrix chain
multiplication problem asks for an ordering (parenthesisation) that minimises
the cost to compute $M$.

The number of orderings is $C_{n-1}=\frac{(2n-2)!}{n!(n-1)!}$, i.e., the
$(n-1)$th Catalan number, which grows exponentially in $n$. Still, the problem
can be solved exactly in $\Theta(n^{3})$ time using a textbook dynamic
programming formulation [10], while the fastest known algorithms runs in
$O(n\log n)$ time [12, 13]. There also exist approximation algorithms with
good (multiplicative) guarantees, some of which run in $O(n)$ time [4, 5].
Refer to Section 2 for an overview of related work.

In this work, we study the matrix chain multiplication problem from a
different perspective by addressing the following questions.

  * •

Q1: Are all orderings _useful_? We say that an ordering is useful if its cost
is strictly lower than the cost of any other ordering for at least one
combination of matrix sizes. Intuitively, each useful ordering is valuable,
since it is the best on at least some instances of the problem.

  * •

Q2: Are all useful orderings _essential_? An ordering is essential if one can
pick a combination of matrix sizes for which the ordering is optimal and the
ratio between its cost and that of the second-best ordering is arbitrarily
large. Intuitively, each essential algorithm is especially important, since
there are instances of the problem on which it is arbitrarily better than the
second best.

  * •

Q3: How important are those orderings (if any) that are useful but non-
essential? An ordering is useful but non-essential if there exists an instance
for which it is optimal, and the cost of the second-best ordering is within a
constant factor. Intuitively, if the factor is provably reduced, the non-
essential orderings can be removed from consideration without large negative
consequences on performance. We ask whether useful but non-essential orderings
exist, and how much one pays, should they be discarded.

We make the following contributions. We address Q1 in Section 4, where we show
that all orderings are indeed useful and, what is more, all are useful on
infinitely many instances of the problem. We address Q2 and Q3 in Section 5,
where we show that $n+1$ specific orderings are essential and all others are
non-essential (though useful). Moreover, we show that constraining the
selection of an ordering to the set of essential orderings results in a
previously published approximation algorithm with an approximation factor of
two. Finally, in Section 6, we present experimental evidence indicating that
i) for most problem instances an essential orderings is optimal, and ii) for
most other instances the penalty of removing all non-essential orderings is
far lower than the theoretical upper bound of twice the optimal cost.

Our results have direct consequences for the construction of compilers of
linear algebra expressions (such as MATLAB, Julia, Linnea [2] and others) in
the common scenario where some or all of the matrix sizes are not known at
compile time. The matrix chains form a subset of all linear algebra
expressions. Therefore, if a compiler excludes any of the essential orderings
from consideration, then the generated code will be arbitrarily far from
optimal for infinite combinations of matrix sizes. On the other hand, if a
compiler excludes all of the exponentially many non-essential orderings and
keeps only the linearly many essential ones, then the code generated for the
matrix chain can be made to never have a cost more than twice the optimal.
Furthermore, on most instances, said output code will either be optimal or
perform much closer to optimality than the bound suggests. In other words, a
compiler for linear algebra expressions with unknown sizes that targets either
matrix chains or any expression containing them must generate code capable of
realising _all_ matrix chain orderings to guarantee optimal cost on every
matrix chain instance. However, if some performance degradation is acceptable,
then the compiler only needs to generate code for the linearly many essential
algorithms.

##  2 Related Work

The matrix chain has been extensively studied in prior works. In 1973, Godbole
published the first work on the matrix chain multiplication problem,
presenting the now classical dynamic programming algorithm that finds the
optimal ordering in $\Theta(n^{3})$ time [10]. In 1982, Yao introduced an
improved version of Godbole’s algorithm with time complexity $O(n^{2})$.
Shortly after this, Hu and Shing published a rather complex algorithm to find
an optimal ordering in $O(n\log n)$ time [12, 13]. A proof for one of their
lemmas was eventually shown to be incorrect, although the result remained
intact after its proof was corrected [18]. Hu and Shing’s work also showed
that the matrix chain multiplication problem can be translated into the
partition of a convex polygon with $n+1$ sides into $n-1$ non-intersecting
triangles (a fact that is recurrently resorted to in the published literature
on the matter). Other works focused on finding the optimal ordering for
instances with particular properties, such as the work of Santoro [17] (an
$O(n)$ algorithm for sparse, square matrices) and Wang et al. [19] (an
$O(n\log m)$ algorithm where $m$ is the number of local minima in the sequence
of dimensions).

Approximation algorithms started to appear soon after Godbole published the
dynamic programming algorithm [10]. In 1975, Chandra presented an
approximation algorithm with an approximation factor of two [4].
(Unfortunately, this work was never published besides as a technical report
that is utterly difficult to access nowadays.) Shortly after this, in 1978,
Chin introduced an $O(n)$ approximation algorithm [5] with an approximation
factor of $1.25$. In 1981, Hu and Shing presented a reformulation of Chin’s
approximation algorithm, though obtained by other means (triangulation of an
$n$-sided polygon), and refined the approximation factor to $1.155$ [11].

Over the years, multi-processor and multi-core architectures became more and
more relevant. Because of this, some published works [6, 16, 3] focused on
parallelising the algorithms to find optimal orderings on multi-processor
architectures. Some others [6, 7] concentrated on approximation algorithms (by
parallelising the algorithm given by Chin and Hu and Shing), also on multi-
processor architectures. Other works focused on the actual evaluation of the
matrix chain on parallel architectures [15]. More recent work has been devoted
to optimising the evaluation of the chain while factoring in inter-processor
communication and distinct matrix multiplication algorithms [20]. It is also
worth mentioning the work in [1], which aimed at mapping matrix chains with
properties (e.g., diagonal, triangular, and symmetric matrices) and operators
(e.g., inversion and transposition) to BLAS [14, 9, 8] kernels.

The common denominator amongst all these works is that they target solutions
to the matrix chain multiplication problem. In this work, we study the problem
from a different perspective. Instead of finding an optimal (or approximate)
ordering for a specific instance, we investigate how the various orderings
perform in relation to each other on the whole set of problem instances. We
find that all orderings have something to contribute and a few are absolutely
essential.

##  3 Preliminaries

In this section, we introduce some basic terminology. Expression (1) is a
_matrix chain_ of length $n$. Let $\mathcal{S}_{n}$ denote the set of
orderings (parenthesisations). Then $|\mathcal{S}_{n}|=C_{n-1}$, the $(n-1)$th
Catalan number. The size of matrix $M_{i}$ is $k_{i-1}\times k_{i}$ for all
$i\in\\{1,2,\ldots,n\\}$. An _instance_ of the matrix chain multiplication
problem (Problem 3.2) is specified by a tuple
$\boldsymbol{k}=(k_{0},k_{1},\ldots,k_{n})$.

######  Definition 3.1 (Cost of a matrix multiplication).

Given three integers $a$, $b$, $c$, the _cost_ of multiplying $(M_{a+1}\cdots
M_{b})$ with $(M_{b+1}\cdots M_{c})$ is given by the function
$\phi_{\boldsymbol{k}}(a,b,c):=\phi(k_{a},k_{b},k_{c})=k_{a}k_{b}k_{c}$.
$\phi$ is monotonically non-decreasing in its arguments and has rotational
symmetry, meaning $\phi(p,q,r)=\phi(r,p,q)$. As a consequence,
$\phi_{\boldsymbol{k}}$ also has rotational symmetry in its arguments.

The cost of an ordering in $\mathcal{S}_{n}$ is given by a sum of $n-1$ terms
$\phi_{\boldsymbol{k}}(a,b,c)$, each with its own triplet
$(a,b,c)\in\\{0,1,\ldots,n\\}^{3}$. An ordering is uniquely represented by the
set $\mathcal{A}$ of index triplets $(a,b,c)$ that appear in its cost
function. Therefore, the cost of an ordering $\mathcal{A}$ on an instance
$\boldsymbol{k}$ can be expressed as

$T(\mathcal{A},\boldsymbol{k})=\sum_{(a,b,c)\in\mathcal{A}}\phi_{\boldsymbol{k}}(a,b,c)=\sum_{(a,b,c)\in\mathcal{A}}\phi(k_{a},k_{b},k_{c}).$

For example, the ordering $\mathcal{A}$ with parenthesisation
$M=((M_{1}M_{2})M_{3})M_{4}$ has the cost function
$T(\mathcal{A},\boldsymbol{k})=k_{0}k_{1}k_{2}+k_{0}k_{2}k_{3}+k_{0}k_{3}k_{4}$.
The index triplet representation is
$\mathcal{A}=\\{(0,1,2),(0,2,3),(0,3,4)\\}$.

The matrix chain multiplication problem can be formalised as follows.

######  Problem 3.2 (Matrix Chain Multiplication Problem).

Given a matrix chain (1) with dimension sequence
$\boldsymbol{k}=(k_{0},k_{1},\ldots,k_{n})$, find an ordering
$\mathcal{A}\in\mathcal{S}_{n}$ such that
$T(\mathcal{A},\boldsymbol{k})=\min_{\mathcal{B}\in\mathcal{S}_{n}}T(\mathcal{B},\boldsymbol{k})$.

If the cost of an ordering is amongst the cheapest ones for a particular
instance, we say that it is optimal (on that instance). If, in addition, no
other ordering has the same cost, then we say that the ordering is uniquely
optimal.

######  Definition 3.3 (Optimal and uniquely optimal orderings).

An ordering $\mathcal{A}$ is _optimal_ on an instance $\boldsymbol{k}$ if
$T(\mathcal{A},\boldsymbol{k})\leq\min_{\mathcal{B}\in\mathcal{S}_{n}\setminus\\{\mathcal{A}\\}}T(\mathcal{B},\boldsymbol{k})$.
The ordering is _uniquely optimal_ if the inequality is strict.

Suppose that some subset $\mathcal{Q}\subset\mathcal{S}_{n}$ of orderings are
removed, i.e., are not allowed to be used to evaluate the matrix chain. The
optimal cost on an instance $\boldsymbol{k}$, when the choice of ordering is
restricted from $\mathcal{S}_{n}$ to $\mathcal{S}_{n}\setminus\mathcal{Q}$,
will either increase or stay the same. The relative increase in cost
quantifies the performance penalty of not being allowed to use the orderings
in $\mathcal{Q}$.

######  Definition 3.4 (Penalty).

The _penalty_ of removing a subset of orderings
$\mathcal{Q}\subset\mathcal{S}_{n}$ is the relative increase (if any) in the
optimal cost and is given by the function

$P(\mathcal{Q},\boldsymbol{k})=\frac{\min_{\mathcal{B}\in\mathcal{S}_{n}\setminus\mathcal{Q}}T(\mathcal{B},\boldsymbol{k})}{\min_{\mathcal{A}\in\mathcal{S}_{n}}T(\mathcal{A},\boldsymbol{k})}-1\in[0,\infty).$

The numerator is the optimal cost amongst all remaining orderings. The
denominator is the optimal cost amongst all orderings.

The penalty is zero if and only if the set of remaining orderings
$\mathcal{S}_{n}\setminus\mathcal{Q}$ contains an optimal ordering.
Intuitively, if the penalty of $\mathcal{Q}$ on instance $\boldsymbol{k}$ is
$x\%$, then the optimal cost when one is not allowed to use the orderings in
$\mathcal{Q}$ increases by $x\%$.

The questions we answer in this paper revolve around the concepts of useful
and essential orderings, informally introduced in the introduction.

######  Definition 3.5 (Useful and essential orderings).

An ordering $\mathcal{A}$ is _useful_ if there exists an instance
$\boldsymbol{k}$ on which $\mathcal{A}$ is uniquely optimal. An ordering
$\mathcal{A}$ is _essential_ if for any $r\in\mathbb{R}^{+}$ there exists an
instance $\boldsymbol{k}$ such that $P(\\{\mathcal{A}\\},\boldsymbol{k})>r$.
In other words, one can choose an instance to make the penalty of removing the
ordering $\mathcal{A}$ arbitrarily large.

##  4 Every ordering is useful

An instance of the matrix chain of length $n$ has $n+1$ parameters and can be
evaluated using any of the exponentially (in $n$) many orderings in
$\mathcal{S}_{n}$. The abundance of orderings suggests that some of them might
be useless, meaning that they are not uniquely optimal on any instance.
However, this is not the case; Theorem 4.5 below shows that every ordering is
useful (Definition 3.5).

To prove this result, we first establish Lemma 4.1.

######  Lemma 4.1.

An ordering that is uniquely optimal on one instance is uniquely optimal on an
infinite number of instances.

######  Proof 4.2.

Let $\boldsymbol{k}=(k_{0},k_{1},\ldots,k_{n})$ be an instance on which
$\mathcal{A}$ is uniquely optimal, that is, for all
$\mathcal{B}\in\mathcal{S}_{n}\setminus\\{\mathcal{A}\\}$,

$\frac{T(\mathcal{B},\boldsymbol{k})}{T(\mathcal{A},\boldsymbol{k})}>1.$

The tuple $\boldsymbol{k}$ can be scaled by a positive integer $\alpha$ so
that

$\boldsymbol{k}^{\prime}=\alpha\boldsymbol{k}=(\alpha k_{0},\alpha
k_{1},\ldots,\alpha k_{n}).$

Thus, $\phi_{\boldsymbol{k}^{{}^{\prime}}}(a,b,c)=(\alpha k_{a})(\alpha
k_{b})(\alpha k_{c})=\alpha^{3}\phi_{\boldsymbol{k}}(a,b,c)$. It follows that
for all $\mathcal{B}\in\mathcal{S}_{n}\setminus\\{\mathcal{A}\\}$,

$\frac{T(\mathcal{B},\boldsymbol{k}^{\prime})}{T(\mathcal{A},\boldsymbol{k}^{\prime})}=\frac{\alpha^{3}T(\mathcal{B},\boldsymbol{k})}{\alpha^{3}T(\mathcal{A},\boldsymbol{k})}=\frac{T(\mathcal{B},\boldsymbol{k})}{T(\mathcal{A},\boldsymbol{k})}>1.$

In other words, $\mathcal{A}$ is uniquely optimal also on
$\boldsymbol{k}^{\prime}$. Since there are infinitely many choices for
$\alpha$, each resulting in a distinct instance, we conclude that there are
infinitely many instances on which $\mathcal{A}$ is uniquely optimal.

We need [5, Theorem 1] (restated and adapted here as Lemma 4.3), which
establishes a sufficient condition for a particular matrix multiplication to
be present in all optimal orderings.

######  Lemma 4.3.

Let $m=\operatorname{arg\,min}_{i}{k_{i}}$ be the index of the smallest
element in $\boldsymbol{k}$. If for some $i\in\\{0,1,\ldots,n\\}$ (taken as
$\pmod{n+1}$) $k_{i}>k_{i-1}$, $k_{i}>k_{i+1}$, and the condition

(2) $\frac{1}{k_{i}}<\frac{1}{k_{i-1}}+\frac{1}{k_{i+1}}-\frac{1}{k_{m}}$

holds, then the multiplication $M_{i}M_{i+1}$ must appear in every optimal
ordering.

######  Proof 4.4.

See [5, Theorem 1].

We are now ready to prove the section’s main result.

######  Theorem 4.5.

Every ordering in $\mathcal{S}_{n}$ is uniquely optimal on infinitely many
instances.

######  Proof 4.6.

The case $n\leq 2$ is trivial, so assume $n\geq 3$. Consider an arbitrary
ordering $\mathcal{A}\in\mathcal{S}_{n}$. We will construct an instance
$\boldsymbol{k}$ on which $\mathcal{A}$ is uniquely optimal. We do so in three
steps. In Step 1, we craft a sequence of increasingly larger positive
integers. In Step 2, we assign values from this sequence to $\boldsymbol{k}$.
At this point, we have constructed _one_ instance on which $\mathcal{A}$ is
uniquely optimal. In Step 3, we apply Lemma 4.1 to show that every ordering is
uniquely optimal on _infinitely_ many instances.

Step 1. Craft a sequence of positive integers. Let
$1=R_{0}<R_{1}<\ldots<R_{n-1}$ be the finite sequence of increasingly larger
positive rational numbers given by

$R_{\ell}=\frac{2^{n}+\ell-n-1}{2^{n}+\ell-n-2^{\ell}},$

where $\ell\in\\{0,1,\ldots,n-1\\}$. For a fixed $n$, the sequence increases
with $\ell$, since the numerator increases and the denominator decreases.
Plus, the sequence is positive since $R_{0}=1$ and $R_{n-1}=2$. If
$\ell_{1},\ell_{2}<\ell$, then

(3)
$\frac{1}{R_{\ell}}<\frac{1}{R_{\ell_{1}}}+\frac{1}{R_{\ell_{2}}}-\frac{1}{R_{0}}.$

To verify this, note that $R_{0}=1$ and $R_{\ell_{1}},R_{\ell_{2}}\leq
R_{\ell-1}$ and hence

$\frac{1}{R_{\ell}}<\frac{2^{n}+\ell-n-2^{\ell}}{2^{n}+\ell-n-2}=\frac{2}{R_{\ell-1}}-\frac{1}{R_{0}}\leq\frac{1}{R_{\ell_{1}}}+\frac{1}{R_{\ell_{2}}}-\frac{1}{R_{0}}.$

Let $c=L_{0}<L_{1}<\cdots<L_{n-1}$, where $L_{\ell}=cR_{\ell}$, be the finite
sequence of increasingly larger integers obtained by scaling $R_{\ell}$ by
$c$, the least common multiple of all denominators in the sequence
$R_{0},R_{1},\ldots,R_{n-1}$. Note that the property (3) holds also for the
integer sequence $L_{0},L_{1},\ldots,L_{n-1}$.

Step 2. Assign values to $k_{i}$ for $i\in\\{0,1,\ldots,n\\}$. To make
$\mathcal{A}$ uniquely optimal, we assign integers from the sequence
$L_{0},L_{1},\ldots,L_{n-1}$ to the elements of $\boldsymbol{k}$ in such a way
that Lemma 4.3 guarantees that every matrix multiplication in $\mathcal{A}$
appears in every optimal ordering. In other words, $\mathcal{A}$ must be
uniquely optimal on $\boldsymbol{k}$.

Identify a matrix multiplication $M_{i}M_{i+1}$ associated together as
determined by $\mathcal{A}$. Set $k_{i}=L_{n-1}$. Replace $M_{i}M_{i+1}$ by
$\hat{M}_{i}:=M_{i}M_{i+1}$ of size $k_{i-1}\times k_{i+1}$ to obtain a
reduced chain of length $n-1$. Repeat this reduction process until all
multiplications have been eliminated.

In the first iteration, $L_{n-1}$ is assigned to some $k_{i_{1}}$. In the
second iteration, $L_{n-2}$ is assigned to some $k_{i_{2}}$. Finally, in the
last iteration, $L_{1}$ is assigned to some $k_{i_{n-1}}$. At this point, all
dimensions $k_{1},k_{2},\ldots,k_{n-1}$ have been assigned an integer from the
sequence $L_{1},\ldots,L_{n-1}$. As a final step, set $k_{0},k_{n}=L_{0}$.
Since the elements of $L$ are assigned from largest to smallest, the
inequality (3) will hold for every three dimensions $k_{i-1},k_{i},k_{i+1}$ in
every matrix multiplication in $\mathcal{A}$. Therefore, each multiplication
in $\mathcal{A}$ must, by Lemma 4.3, be present in every optimal ordering.
Since there is only one such ordering, $\mathcal{A}$ must be uniquely optimal
on $\boldsymbol{k}$.

Step 3. From one to infinitely many instances. By Lemma 4.1, it follows that
$\mathcal{A}$ is uniquely optimal on infinitely many instances.

##  5 Few orderings are essential

In this section, we show that only a few of the orderings are essential by
identifying the set of essential orderings for a matrix chain of length $n$.

Let $\mathcal{E}_{n}$ denote the set of orderings of the form

$(M_{1}(M_{2}\cdots(M_{h-1}M_{h})\cdots))\;\big{|}\;((\cdots(M_{h+1}M_{h+2})\cdots
M_{n-1})M_{n}),$

where $h\in\\{0,1,\ldots,n\\}$. For $h=0$ the ordering is left-to-right; for
$h=n$ it is right-to-left. Due to the pattern of association fanning out in
both directions from the dividing line at dimension $k_{h}$, we say that these
orderings _fan out_ from dimension $k_{h}$. We let
$\mathcal{E}_{n,h}\in\mathcal{E}_{n}$ denote the ordering that fans out from
$k_{h}$. There are $n+1$ orderings of this type. For $n\geq 4$, they are all
distinct, however, due to symmetry, there are only $n-1$ distinct orderings
for $n\leq 3$. More precisely,

$|\mathcal{E}_{n}|=\begin{cases}n-1&\text{if $n\leq 3$,}\\\
n+1&\text{otherwise.}\end{cases}$

We will show that all orderings in $\mathcal{E}_{n}$ are essential (Definition
3.5) and that no other orderings are essential. Therefore, $\mathcal{E}_{n}$
is _the_ set of essential orderings for a matrix chain of length $n$.

The following lemma shows that all orderings in $\mathcal{E}_{n}$ are
essential.

######  Lemma 5.1.

For any $r\in\mathbb{R}^{+}$ and $\mathcal{E}_{n,h}\in\mathcal{E}_{n}$, there
are infinitely many instances $\boldsymbol{k}$ for which
$P(\\{\mathcal{E}_{n,h}\\},\boldsymbol{k})>r$.

######  Proof 5.2.

Consider an instance of the form
$\boldsymbol{k}=(\alpha,\ldots,\alpha,1,\alpha,\ldots,\alpha)$, where $\alpha$
is a positive integer greater than one and $k_{h}=1$. The cost of
$\mathcal{E}_{n,h}$ on $\boldsymbol{k}$ is

$T(\mathcal{E}_{n,h},\boldsymbol{k})=\sum_{1}^{n-1}1\cdot\alpha\cdot\alpha=(n-1)\alpha^{2}.$

Only $\mathcal{E}_{n,h}$ has $k_{h}$ appearing in each of the $n-1$ terms of
the cost function. Any other ordering has somewhere between $1$ and $n-2$
terms in its cost function containing $k_{h}$. Since $\alpha>1$, the cost is
minimised by maximising the number of terms containing $k_{h}$. Therefore, let
$\mathcal{B}\neq\mathcal{E}_{n,h}$ be an ordering for which $k_{h}$ appears in
$n-2$ terms of the cost function. Its cost on $\boldsymbol{k}$ is

$T(\mathcal{B},\boldsymbol{k})=\alpha\cdot\alpha\cdot\alpha+\sum_{1}^{n-2}1\cdot\alpha\cdot\alpha=\alpha^{3}+(n-2)\alpha^{2}.$

Such an ordering always exists. The penalty of removing $\mathcal{E}_{n,h}$ on
$\boldsymbol{k}$ is

$\begin{split}P(\\{\mathcal{E}_{n,h}\\},\boldsymbol{k})&=\frac{\min_{\mathcal{A}\in\mathcal{S}_{n}\setminus\\{\mathcal{E}_{n,h}\\}}T(\mathcal{A},\boldsymbol{k})}{T(\mathcal{E}_{n,h},\boldsymbol{k})}-1=\frac{T(\mathcal{B},\boldsymbol{k})}{T(\mathcal{E}_{n,h},\boldsymbol{k})}-1\\\
&=\frac{\alpha^{3}+(n-2)\alpha^{2}}{(n-1)\alpha^{2}}-1=\frac{\alpha}{n-1}+\frac{n-2}{n-1}-1=\Theta(\alpha).\end{split}$

Since the penalty grows without bound as $\alpha\to\infty$, for any
$r\in\mathbb{R}^{+}$ we can choose $\alpha$ large enough to make the penalty
greater than $r$. By Lemma 4.1, there are infinitely many instances with the
same penalty.

Lemma 5.1 shows that every ordering in $\mathcal{E}_{n}$ is essential.
However, this does not imply that every other ordering is non-essential. The
following lemma shows that an ordering $\mathcal{E}_{n,h}$, where $h$ is
chosen such that $k_{h}$ is the smallest element in $\boldsymbol{k}$, has a
cost that is strictly less than twice the optimal cost. The result is due to
Chandra [4, Theorem 3]. We improve on the exposition of the proof.

######  Lemma 5.3.

Let $\mathcal{A}$ be an optimal ordering on instance $\boldsymbol{k}$, and
$m=\operatorname{arg\,min}_{i}{k_{i}}$, then
$T(\mathcal{E}_{n,m},\boldsymbol{k})<2T(\mathcal{A},\boldsymbol{k})$.

######  Proof 5.4.

The case $n\leq 2$ is trivial, so assume $n\geq 3$. Let $T_{\rm
opt}:=T(\mathcal{A},\boldsymbol{k})$. We show that
$T(\mathcal{E}_{n,m},\boldsymbol{k})<D\leq 2T_{\rm opt}$, where $D$ is the
conveniently chosen sum

$D:=\sum_{i\in\\{0,1,\ldots,n\\}}\phi_{\boldsymbol{k}}(i-1,i,m).$

Here, and in the rest of the proof, all arguments to $\phi_{\boldsymbol{k}}$
are taken modulo $n+1$. For instance, the term in $D$ for $i=0$ is
$\phi_{\boldsymbol{k}}(n,0,m)$. We will first show that $D\leq 2T_{\rm opt}$
(Step 1) and then show that $T(\mathcal{E}_{n,m},\boldsymbol{k})<D$ (Step 2).
We first make an observation.

Observation 1. Every matrix $M_{i}$ appears in one and only one
multiplication. If $M_{i}$ appears as the left operand ($M_{i}X$ for some
$X=\prod_{j=i+1}^{z}M_{j}$), then the term $\phi_{\boldsymbol{k}}(i-1,i,z)$
appears in the cost. In this case, the dimension $k_{i}$ is eliminated and
hence no other term can contain the argument $i$. If instead $M_{i}$ appears
as the right operand ($XM_{i}$ for some $X=\prod_{j=z}^{i-1}M_{j}$), then the
term $\phi_{\boldsymbol{k}}(z,i-1,i)$ appears in the cost. In this case, the
dimension $k_{i-1}$ is eliminated and hence no other term can contain the
argument $i-1$. In conclusion, for any ordering there is one and only one term
in its cost function that contains both $i-1$ and $i$ for
$i\in\\{1,2,\ldots,n\\}$. The last multiplication in any ordering takes the
form $(M_{1}\cdots M_{z})(M_{z+1}\cdots M_{n})$ for some $1\leq z\leq n-1$.
This multiplication adds the term
$\phi_{\boldsymbol{k}}(0,z,n)=\phi_{\boldsymbol{k}}(n,0,z)$ (mind the modulo
and rotation in the arguments) to the cost. As a result, for each
$i\in\\{0,1,\ldots,n\\}$, $T_{\rm opt}$ has one and only one term of the form
$\phi_{\boldsymbol{k}}(i-1,i,z)$.

Step 1. $D\leq 2T_{\rm opt}$. The proof is based on a matching of every term
in $D$ with some term in $2T_{\rm opt}$ in such a way that each term in $D$ is
less than or equal to its matched term in $2T_{\rm opt}$. We can then conclude
that $D\leq 2T_{\rm opt}$.

Let $\sigma$ be the function that for each $i\in\\{0,1,\ldots,n\\}$ maps a
term of the form $\phi_{\boldsymbol{k}}(i-1,i,m)$ in $D$ to a term of the form
$\phi_{\boldsymbol{k}}(i-1,i,z)$ in $T_{\rm opt}$. As a consequence of
Observation 1, the function is well-defined, since there is one and only one
term of the specified form in $T_{\rm opt}$.

Consider any term $t$ in $T_{\rm opt}$. We show that there are only three
cases regarding how $\sigma$ maps terms in $D$ to terms in $T_{\rm opt}$:

  * •

$\sigma$ maps _none_ of the terms in $D$ to $t$. This happens if and only if
there is no pair of consecutive indices in $t$. That is, if
$t=\phi_{\boldsymbol{k}}(a,b,c)$ then $a+1\not\equiv b\pmod{n+1}$,
$b+1\not\equiv c\pmod{n+1}$, and $c+1\not\equiv a\pmod{n+1}$.

  * •

$\sigma$ maps _one_ term in $D$ to $t$. This happens if and only if there is
exactly one consecutive pair of indices in $t$.

  * •

$\sigma$ maps _two_ terms in $D$ to $t$. This happens if and only if $t$ is of
the form $\phi_{\boldsymbol{k}}(i-1,i,i+1)$ for some $i$ (modulo $n+1$).

The function $\sigma$ cannot map _more_ than two terms in $D$ to $t$ when
$n\geq 3$ since the system of congruences $a+1\equiv b\pmod{n+1}$, $b+1\equiv
c\pmod{n+1}$, and $c+1\equiv a\pmod{n+1}$ does not have a solution when $n\geq
3$. (If $n=2$, then $a,b,c=0,1,2$ satisfies the conditions and there are
_three_ pairs of consecutive indices: $(0,1)$, $(1,2)$, and $(0,2)$.) This
way, $\sigma$ maps _at most_ two terms in $D$ to each term in $T_{\rm opt}$.
Since $\sigma$ is well-defined, every term in $D$ is mapped to some term in
$T_{\rm opt}$, but not every term in $T_{\rm opt}$ is necessarily mapped to by
any term in $D$.

Since $2T_{\rm opt}=T_{\rm opt}+T_{\rm opt}$ has two copies of each term and
$\sigma$ never maps _more_ than two terms in $D$ to the same term in $T_{\rm
opt}$, each term in $D$ can be matched with a term in $2T_{\rm opt}$ such that
no term in the latter is matched more than once. Each pair established in this
way has the form $\phi_{\boldsymbol{k}}(i-1,i,m)$ in $D$ and
$\phi_{\boldsymbol{k}}(i-1,i,z)$ in $T_{\rm opt}$. Since $k_{m}$ is the
smallest element in $\boldsymbol{k}$ and the function $\phi$ is monotonically
non-decreasing (recall Definition 3.1),
$\phi_{\boldsymbol{k}}(i-1,i,m)\leq\phi_{\boldsymbol{k}}(i-1,i,z)$. Therefore,
$D\leq 2T_{\rm opt}$.

Step 2. $T(\mathcal{E}_{n,m},\boldsymbol{k})<D$. The cost of
$\mathcal{E}_{n,m}$ on $\boldsymbol{k}$ is given by

$T(\mathcal{E}_{n,m},\boldsymbol{k})=\sum_{i\in\\{0,1,\ldots,n\\}\setminus\\{m,m+1\\}}\phi_{\boldsymbol{k}}(i-1,i,m).$

Every term in $T(\mathcal{E}_{n,m},\boldsymbol{k})$ also appears in $D$. Since
$D$ has strictly more terms, $T(\mathcal{E}_{n,m},\boldsymbol{k})<D$.

By combining Steps 1 and 2, it follows that
$T(\mathcal{E}_{n,m},\boldsymbol{k})<2T_{\rm opt}$.

Notice that Lemma 5.3 holds as long as $\phi$ is monotonically non-decreasing
and has rotational symmetry in its arguments, since the proof is based on
matching terms from different cost expressions, not on the actual evaluation
of $\phi$.

Figure 1 illustrates the two layers of matching of terms in the proof of Lemma
5.3 for the case $m=3$ and the optimal ordering
$((M_{1}M_{2})((M_{3}(M_{4}M_{5}))M_{6}))(M_{7}M_{8})$. The terms of $2T_{\rm
opt}$ are on the top two rows, the terms of $D$ are on the middle row, and the
terms of $T(\mathcal{E}_{n,m},\boldsymbol{k})$ are depicted at the bottom.
Every term of $D$ has been matched (one-to-one) using $\sigma$ with a term of
$2T_{\rm opt}$ that is equal or greater. Similarly, every term of
$T(\mathcal{E}_{n,m},\boldsymbol{k})$ has been matched with its identical term
in $D$.

$(0,1,2)$$(0,2,6)$$(2,3,5)$$(3,4,5)$$(2,5,6)$$(0,6,8)$$(6,7,8)$$(0,1,2)$$(0,2,6)$$(2,3,5)$$(3,4,5)$$(2,5,6)$$(0,6,8)$$(6,7,8)$$(8,0,3)$$i=0$$(0,1,3)$$i=1$$(1,2,3)$$i=2$$(2,3,3)$$i=3$$(3,4,3)$$i=4$$(4,5,3)$$i=5$$(5,6,3)$$i=6$$(6,7,3)$$i=7$$(7,8,3)$$i=8$$(0,3,8)$$(0,1,3)$$(1,2,3)$$(3,4,5)$$(3,5,6)$$(3,6,7)$$(3,7,8)$
Figure 1: Example of term matching between $2T_{\rm opt}$ (above), $D$
(middle), and $T(\mathcal{E}_{n,m},\boldsymbol{k})$ (bottom).

The following theorem shows that the penalty of removing every ordering _not_
in $\mathcal{E}_{n}$ is bounded by $100\%$. In other words, only the orderings
in $\mathcal{E}_{n}$ are essential. Even though all other orderings are useful
according to Theorem 4.5, the penalty of removing them is low (no worse than
twice the optimal cost) even in the worst case.

######  Theorem 5.5.

The maximum penalty of removing every ordering not in $\mathcal{E}_{n}$ is
below $100\%$, i.e.,
$\max_{\boldsymbol{k}}{P(\mathcal{S}_{n}\setminus\mathcal{E}_{n},\boldsymbol{k})}<100\%$.

######  Proof 5.6.

Let $m=\operatorname{arg\,min}_{i}{k_{i}}$. Then

$\begin{split}P(\mathcal{S}_{n}\setminus\mathcal{E}_{n},\boldsymbol{k})&=\frac{\min_{\mathcal{B}\in\mathcal{S}_{n}\setminus(\mathcal{S}_{n}\setminus\mathcal{E}_{n})}T(\mathcal{B},\boldsymbol{k})}{\min_{\mathcal{A}\in\mathcal{S}_{n}}T(\mathcal{A},\boldsymbol{k})}-1=\frac{\min_{\mathcal{B}\in\mathcal{E}_{n}}T(\mathcal{B},\boldsymbol{k})}{\min_{\mathcal{A}\in\mathcal{S}_{n}}T(\mathcal{A},\boldsymbol{k})}-1\\\
&\leq\frac{T(\mathcal{E}_{n,m},\boldsymbol{k})}{\min_{\mathcal{A}\in\mathcal{S}_{n}}T(\mathcal{A},\boldsymbol{k})}-1<2-1=100\%.\end{split}$

The final inequality follows from Lemma 5.3.

The following theorem establishes our main result.

######  Theorem 5.7.

All orderings in $\mathcal{E}_{n}$ are essential and no other orderings are
essential.

######  Proof 5.8.

By Lemma 5.1, all orderings in $\mathcal{E}_{n}$ are essential. By Theorem
5.5, no ordering in $\mathcal{S}_{n}\setminus\mathcal{E}_{n}$ is essential.

##  6 Experiments

The theoretical results presented in the previous two sections establish that
$\mathcal{E}_{n}$ is _the_ set of essential orderings and that removing every
other ordering leads to a penalty bounded above by $100\%$. However, the
theoretical analysis does not say anything about _how often_ one of the
essential algorithms is optimal. Nor does it shed any light on the _average_
penalty caused by removing all non-essential orderings. To address these
quantitative questions, we performed the following experiment.

For all $n\in\\{2,3,\ldots,9\\}$, we randomly sampled one million instances
(with replacement) of a matrix chain multiplication problem of length $n$.
Each dimension $k_{i}$, for $i=0,1,\ldots,n$, was chosen at random from a
uniform distribution from $1$ to $1000$. For each instance $\boldsymbol{k}$,
we recorded the penalty of removing every non-essential ordering, i.e.,
$P(\mathcal{S}_{n}\setminus\mathcal{E}_{n},\boldsymbol{k})$. Let
$\mathcal{P}_{n}$ denote the set of samples ($|\mathcal{P}_{n}|=10^{6}$), and
let $\mathcal{P}_{n}^{+}\subseteq\mathcal{P}_{n}$ denote the subset of samples
with a non-zero penalty.

$n$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---
$|\mathcal{S}_{n}|$ | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430
$|\mathcal{E}_{n}|$ | 1 | 2 | 5 | 6 | 7 | 8 | 9 | 10
$|\mathcal{P}_{n}^{+}|/|\mathcal{P}_{n}|$ | 0% | 0% | 0% | 7.9% | 10.1% | 11.2% | 11.8% | 12.2%
Table 1: Fraction of sampled instances where removing every non-essential
ordering resulted in a non-zero penalty.

The last row of Table 1 shows the fraction of the samples for which the
penalty of removing every non-essential orderings was non-zero. For all other
samples, the penalty is zero, which implies that one or more of the essential
orderings is optimal. These results reveal that for most instances ($>87\%$
when $n\leq 9$), an essential ordering was optimal. That is, not only are
these orderings essential, but also one of them (not always the same one) is
almost always optimal. The fraction of samples with non-zero penalty increases
with $n$ and appears to be asymptotically bounded by some small constant.
However, we have been unable to prove that this is the case as $n\to\infty$.

Figure 2: Estimated distributions of the penalty when every non-essential
ordering is removed for uniform random sampling and $n\in\\{5,6,\ldots,9\\}$.
The cases with a penalty of $0\%$ are not included.

Figure 2 shows a violin plot of the sample distributions of the penalty
restricted to $\mathcal{P}_{n}^{+}$ for $n\in\\{5,6,\ldots,9\\}$ (for $n\leq
4$, every ordering is essential, so $\mathcal{P}_{n}^{+}$ is empty). Theorem
5.5 implies that the penalty of removing every non-essential ordering is
bounded above by $100\%$, but as these results reveal, in practice the penalty
is often much closer to $0\%$. The mean (non-zero) penalty is $<4\%$ for each
$n$ in Figure 2. For $>99\%$ of the samples in $\mathcal{P}_{n}^{+}$, the
penalty is $<20\%$ (for each $n$). In the few cases (around $10\%$) where the
penalty is non-zero, the penalty is almost always $<20\%$, which is far better
than the theoretical upper bound of $100\%$ (Theorem 5.5). If we consider all
samples (i.e., $\mathcal{P}_{n}$ instead of $\mathcal{P}_{n}^{+}$), then in
$>99\%$ of the samples, the penalty is $<10\%$.

##  7 Conclusions

In this article, we consider the problem of multiplying a chain of $n$
matrices, and study how the $C_{n-1}$ orderings behave on the input space. We
posed a series of interrelated questions whose answers have implications for
linear algebra compilers in the common scenario where the sizes of the
matrices are not known at compile time. First, we showed that every ordering
out of the exponentially many is useful, i.e., uniquely optimal, on an
infinite number of instances. Thus, a linear algebra compiler that aims at
generating optimal code for all instances cannot discard any of the
exponentially many orderings.

Assuming that such a generation is unfeasible or that a certain loss in
performance is acceptable, the set of orderings can and must be reduced. The
selected reduced set of orderings should contain those that for some instance
can be uniquely optimal and arbitrarily cheaper than any other, if such
orderings exist. We proved that only $n+1$ orderings fall within this
category, i.e., are essential, and that the penalty for discarding every non-
essential ordering is bounded above by $100\%$. Therefore, if the subset of
orderings is carefully chosen, by retaining $n+1$ orderings and discarding all
the other exponentially many, a compiler can generate code that never performs
more than double the optimal number of operations.

Additionally, we also presented experimental evidence indicating that (for
$n\leq 9$) on most instances ($>87\%$) some essential ordering is optimal.
Moreover, in the few instances where no essential ordering is optimal, the
penalty is in practice much closer to $0\%$ than to its theoretical upper
bound of $100\%$, with an average penalty of $4\%$. These results support that
reducing the set of orderings from $C_{n-1}$ to the linearly many essential
ones and selecting one therein the obtained order of execution is optimal for
most combinations of operand sizes or has a negligible increase over the
optimal cost.

In summary, although every ordering for the matrix chain is uniquely optimal
for some instance, a compiler for linear algebra expressions can constrain the
code generation to only the $n+1$ essential orderings with guarantees that the
evaluation is almost always performed with near-optimal cost.

## Acknowledgments

## References

  * [1] H. Barthels, M. Copik, and P. Bientinesi, The generalized matrix chain algorithm, in Proceedings of the 2018 International Symposium on Code Generation and Optimization, ACM, 2018, pp. 138–148.
  * [2] H. Barthels, C. Psarras, and P. Bientinesi, Linnea: Automatic generation of efficient linear algebra programs, ACM Transactions on Mathematical Software (TOMS), 47 (2021), pp. 1–26.
  * [3] P. G. Bradford, G. J. Rawlins, and G. E. Shannon, Efficient matrix chain ordering in polylog time, SIAM Journal on Computing, 27 (1998), pp. 466–490.
  * [4] A. Chandra, Computing matrix chain products in near-optimal time, Tech. Report RC-5625 (#24393), IBM Thomas J. Watson Research Center, P. O. Box 218, Yorktown Heights, New York, USA, 1975.
  * [5] F. Y. Chin, An o(n) algorithm for determining a near-optimal computation order of matrix chain products, Communications of the ACM, 21 (1978), pp. 544–549.
  * [6] A. Czumaj, Parallel algorithm for the matrix chain product and the optimal triangulation problems, Lecture Notes in Computer Science, (1993), pp. 294–294.
  * [7] A. Czumaj, Very fast approximation of the matrix chain product problem, Journal of Algorithms, 21 (1996), pp. 71–79.
  * [8] J. J. Dongarra, J. Du Croz, S. Hammarling, and I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), 16 (1990), pp. 1–17.
  * [9] J. J. Dongarra, J. Du Croz, S. Hammarling, and R. J. Hanson, A proposal for an extended set of fortran basic linear algebra subprograms, ACM Signum Newsletter, 20 (1985), pp. 2–18.
  * [10] S. S. Godbole, On efficient computation of matrix chain products, IEEE Transactions on Computers, 100 (1973), pp. 864–866.
  * [11] T. Hu and M. Shing, An o (n) algorithm to find a near-optimum partition of a convex polygon, Journal of Algorithms, 2 (1981), pp. 122–138.
  * [12] T. Hu and M. Shing, Computation of matrix chain products. part i, SIAM Journal on Computing, 11 (1982), pp. 362–373.
  * [13] T. C. Hu and M. Shing, Computation of matrix chain products. part ii, SIAM Journal on Computing, 13 (1984), pp. 228–251.
  * [14] C. L. Lawson, R. J. Hanson, D. R. Kincaid, and F. T. Krogh, Basic linear algebra subprograms for fortran usage, ACM Transactions on Mathematical Software (TOMS), 5 (1979), pp. 308–323.
  * [15] H. Lee, J. Kim, S. J. Hong, and S. Lee, Processor allocation and task scheduling of matrix chain products on parallel systems, IEEE Transactions on Parallel and Distributed Systems, 14 (2003), pp. 394–407.
  * [16] P. Ramanan, An efficient parallel algorithm for the matrix-chain-product problem, SIAM Journal on Computing, 25 (1996), pp. 874–893.
  * [17] N. Santoro, Chain mulitplication of matrices of approximately or exactly the same size, Communications of the ACM, 27 (1984), pp. 152–156.
  * [18] O. Schwartz and E. Weiss, Revisiting “computation of matrix chain products”, SIAM Journal on Computing, 48 (2019), pp. 1481–1486.
  * [19] X. Wang, D. Zhu, and J. Tian, Efficient computation of matrix chain, in 2013 8th International Conference on Computer Science & Education, IEEE, 2013, pp. 703–707.
  * [20] E. Weiss and O. Schwartz, Computation of matrix chain products on parallel machines, in 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2019, pp. 491–500.