It is, of course, possible to perform the calculation of entanglement measures on any ordinary computer and the algorithm used will then be, of course, classical.It's just linear algebra.

There are 2 stages involved: first one is a quantum interaction with the system in question (i.e. a measurement, quantum tomography etc), then the second is analyzing the statistics (which boils down to crunching numbers, i.e. feeding the results of the measurements to a classical computer). So the algorithm really comes into play after you perform some kind of quantum interaction with the system you're trying to characterize. 

The first systematic methods of checking entanglement

of a given state was worked out in terms of finding

the decomposition onto separable and entangled parts

of the state see Lewenstein and Sanpera, 1998 and generalizations

to the case of PPT states Kraus et al., 2000;

Lewenstein et al., 2001. The methods were based on the

systematic application of the range criterion involving,

however, the difficult analytical part of finding product

states in the range of a matrix. A further attempt to

provide an algorithm deciding entanglement was based

on checking the variational problem based on a concurrence

vector Audenaert, Verstraeter, et al., 2001. The

problem of the existence of a classical algorithm that

unavoidably identifies entanglement has been analyzed

by Doherty et al. 2002, 2004 both theoretically and numerically

and implemented by semidefinite programming

methods. This approach is based on a theorem

concerning the symmetric extensions of a bipartite quantum

state Fannes et al., 1988; Raggio and Werner, 1989.

It has the following interpretation. For a given bipartite

state AB one asks about the existence of a hierarchy of

symmetric extensions, i.e., whether there exists a family

of states AB1¯Bn with n arbitrary high such that ABi

=AB for all i=1, . . . ,n. It happens that the state AB is

separable if and only if such a hierarchy exists for each

natural n see Sec. XVI. However, for any fixed n

checking the existence of such a symmetric extension is

equivalent to an instance of semidefinite programming.

This leads to an algorithm consisting of checking the

above extendability for increasing n, which always stops

if the initial state AB is entangled. However, the algorithm

never stops if the state is separable. Further, another

hierarchy has been provided together with the corresponding

algorithm in Eisert et al. 2004, extended to

involve higher order polynomial constraints and to address

the multipartite entanglement question.

The idea of the dual algorithm was provided by

Hulpke and Bruß 2005, based on the observation that

in checking the separability of a given state it is enough

to consider a countable set of product vectors spanning

the range of the state. The constructed algorithm is dual

to that described above, in the sense that its termination

is guaranteed if the state is separable, otherwise it will

not stop. It has been further realized that running both

the algorithms i.e., the one that always stops if the state

is entangled with the one that stops if the state is separable

in parallel gives an algorithm that always stops

and decides entanglement definitely Hulpke and Bruß,

2005.

The complexity of both algorithms is exponential in

the size of the problem. It seems that it must be so. The

milestone result that has been proven in a meantime was

that solving separability is a so-called NP hard problem

Gurvits, 2002, 2003, 2004. Namely, it is known Yudin

and Nemirovskii, 1976 that if a largest ball contained in

the convex set scales properly, and moreover there exists

an efficient algorithm for deciding membership, then

one can efficiently minimize linear functionals over the

convex set. Now, Gurvits has shown that for some entanglement

witness corresponding to linear functional

the optimization problem was intractable. This, together

with the results on the radius of the ball contained

within separable states see Sec. X, shows that the problem

of separability cannot be efficiently solved.

Recently the new algorithm via the analysis of a weak

membership problem has been developed together with

analysis of NP hardness Ioannou et al., 2004; Ioannou

and Travaglione, 2006; Ioannou, 2007. The goal of the

algorithm is to solve the “witness” problem. This is either

i to write a separable decomposition up to the

given precision or ii to find an according to a slightly

modified definition entanglement witness that separates

the state from a set of separable states by more than

the notion of the separation is precisely defined. The

analysis shows that one can find more precisely a likely

entanglement witness that detects the entanglement of

the state or find that it is impossible reducing the set of

“good” i.e., possibly detecting the state entanglement

witnesses by each step of the algorithm. The algorithm

singles out a subroutine which can be, to some extent,

interpreted as an oracle calculating a “distance” of the

given witness to the set of separable states.

Finally, note that there are also other proposals of algorithms

deciding separability like Zapatrin 2005 for a

review, see Ioannou, 2007, and references therein.

Quantum entanglement is a quantum mechanical notion, hence valid only within the domain of application of quantum mechanics. This implies a requirement to be met by measurements testing quantum entanglement: they should be sensitive to quantum mechanical information.

Note that this answer is in disagreement with Bohr's dictum that also within the domain of quantum mechanics measuring instruments should be described classically. It should be realized, however, that present-day experimentation is quite a bit more sophisticated than at the time Bohr developed the Copenhagen interpretation of quantum mechanics.

Willem de Muynck

Entanglement (it's quantum-there isn't anything called ``classical entanglement'') can be calculated. *This* ¨calculation can be carried out on a classical computer. The only question is how *efficiently* it can be done, in comparison to a (for the moment hypothetical) quantum computer. The answer is that, for the moment any such calculation is realized, in practice, by classical algorithms, running on classical computers. When a quantum computer becomes available it will be interesting to understand how to program it efficiently, so that the calculation of entanglement measures is, indeed, more efficient than on a classical computer.

There's no obstacle of principle  in encoding qubits on a classical computer, or the linear transformations that represent quantum gates.

Classical Entanglement

It exists of course: knots for example are entangled ropes.

Beyond wordplay, this, however, is irrelevant and misleading  for  the representation and computation of a measure of entanglement of a quantum system-that's the topic of discussion. How words are used depends on the context-and their content.

The classical limit of entanglement measures doesn't coincide with knot invariants: indeed, (quantum) entanglement is, apparently, described by (certain)  knot invariants: http://homepages.math.uic.edu/~kauffman/Quanta.pdf that can be computed classically-but the point is, precisely, indistinguishability, which is a property that doesn't have a classical analog (but whose consequences can be taken into account in a classical computation).