Special Case: As suggested by a Comment of Jernej, suppose that $Q = D - J$ where $J$ as before is the (rank 1) matrix of all ones and $D=\text{diag}(d_1,\ldots,d_n)$ is a nonsingular (positive) diagonal matrix. Indeed for the proposed application in graph theory these would be integer matrices. Then an explicit formula for $\det(Q)$ is:

$$ \det(Q) = \left(\prod_{i=1}^n d_i \right)\left(1 - \sum_{i=1}^n d_i^{-1} \right) $$

A sketch of its proof affords an opportunity to illustrate wider applicability, i.e. whenever $D$ has a known determinant and the system $Dv = (1\ldots 1)^T$ is quickly solved. Begin by factoring out:

$$ \det(D - J) = \det(D) \cdot \det(I - D^{-1}J) $$

Now $D^{-1}J$ is again rank 1, namely $(d_1^{-1}\ldots d_n^{-1})^T(1\ldots 1)$. Note that the second determinant is simply:

$$ f(1) = \det(I- D^{-1}J) $$

where $f(x)$ is the characteristic polynomial of $D^{-1}J$. As a rank 1 matrix, $f(x)$ must have (at least) $n-1$ factors of $x$ to account for its nullspace. The "missing" eigenvalue is $\sum d_i^{-1}$, as may be seen from the computation:

$$ D^{-1}J\; (d_1^{-1}\ldots d_n^{-1})^T = \left(\sum d_i^{-1} \right) (d_1^{-1}\ldots d_n^{-1})^T $$

It follows that the characteristic polynomial $f(x) = x^{n-1} (x - \sum d_i^{-1})$, and $f(1)$ is as shown above for $\det(I - D^{-1}J)$, $1 - \sum d_i^{-1}$.

Also note that if $Q = D-J$, then $12I - Q - J = 12I - D + J - J = 12I - D$, a diagonal matrix whose determinant is simply the product of its diagonal entries.

Without some information about the construction of these $12\times 12$ positive definite real symmetric matrices, the suggestions to be made are of necessity fairly limited.

I downloaded the Armadillo package from Sourceforge and took a look at the documentation. Try to improve performance of separately computing $\det(Q)$ and $\det(12I - Q - J)$, where $J$ is the rank one matrix of all ones, by setting e.g det(Q,slow=false). The documentation notes that this is the default for matrices up to size $4\times 4$, so by omission I assume the slow=true option is a default for the $12\times 12$ case.

What slow=true presumably does is partial or full pivoting in getting a row echelon form, from which the determinant is easily found. However you know in advance the matrix $Q$ is positive definite, so pivoting is unnecessary for stability (at least presumptively for the bulk of your computations. It's unclear if the Armadillo package throws an exception if the pivots become unduly small, but this should be a feature of a reasonable numerical linear algebra package.

The other point would be to follow their recommendation of building the Armadillo package linking to high speed replacements for BLAS and LAPACK, if you are indeed using those; see Sec. 5 of the Armadillo README.TXT file for details. [The use of a dedicated 64-bit version of BLAS or LAPACK is also recommended for speed on current 64-bit machines.]

Row reduction to echelon form is essentially Gaussian elimination, and has arithmetic complexity $\frac{2}{3} n^3 + O(n^2)$. For both matrices this then amounts to twice that work, or $\frac{4}{3} n^3 + O(n^2)$. These operations may well be the "bottleneck" in your processing, but there's little hope that without special structure in $Q$ (or some known relationships among the trillion test cases allowing amortization) the work could be reduced to $O(n^2)$.

For comparison, expansion by cofactors of a general $n\times n$ matrix involves $n!$ multiplication operations (and roughly as many additions/subtractions), so for $n=12$ the comparison ($12! = 479001600$ vs. $\frac{2}{3} n^3 = 1152$) clearly favors elimination over cofactors.

Another approach requiring $\frac{4}{3} n^3 + O(n^2)$ work would be reducing $Q$ to tridiagonal form with Householder transformations, which also puts $12I - Q$ into tridiagonal form. Computing $\det(Q)$ and $\det(12I - Q - J)$ can thereafter be done in $O(n)$ operations. [The effect of the rank one update $-J$ in the second determinant can be expressed as a scalar factor given by solving one tridiagonal system.]

Implementing such an independent computation might be worthwhile as a check on the results of successful (or failed) calls to Armadillo's det function.

Without some information about the construction of these $12\times 12$ positive definite real symmetric matrices, the suggestions to be made are of necessity fairly limited.

I downloaded the Armadillo package from Sourceforge and took a look at the documentation. Try to improve performance of separately computing $\det(Q)$ and $\det(12I - Q - J)$, where $J$ is the rank one matrix of all ones, by setting e.g det(Q,slow=false). The documentation notes that this is the default for matrices up to size $4\times 4$, so by omission I assume the slow=true option is a default for the $12\times 12$ case.

What slow=true presumably does is partial or full pivoting in getting a row echelon form, from which the determinant is easily found. However you know in advance the matrix $Q$ is positive definite, so pivoting is unnecessary for stability (at least presumptively for the bulk of your computations. It's unclear if the Armadillo package throws an exception if the pivots become unduly small, but this should be a feature of a reasonable numerical linear algebra package. EDIT: I found the Armadillo code that implements det in header file include\armadillo_bits\auxlib_meat.hpp, using C++ templates for substantial functionality. The setting slow=false doesn't appear to affect how a $12\times 12$ determinant will be done because the computation gets "thrown over a wall" to LAPACK (or ATLAS) at that point with no indication that pivoting is not required; see det_lapack and its invocations in that file.

The other point would be to follow their recommendation of building the Armadillo package linking to high speed replacements for BLAS and LAPACK, if you are indeed using those; see Sec. 5 of the Armadillo README.TXT file for details. [The use of a dedicated 64-bit version of BLAS or LAPACK is also recommended for speed on current 64-bit machines.]

Row reduction to echelon form is essentially Gaussian elimination, and has arithmetic complexity $\frac{2}{3} n^3 + O(n^2)$. For both matrices this then amounts to twice that work, or $\frac{4}{3} n^3 + O(n^2)$. These operations may well be the "bottleneck" in your processing, but there's little hope that without special structure in $Q$ (or some known relationships among the trillion test cases allowing amortization) the work could be reduced to $O(n^2)$.

For comparison, expansion by cofactors of a general $n\times n$ matrix involves $n!$ multiplication operations (and roughly as many additions/subtractions), so for $n=12$ the comparison ($12! = 479001600$ vs. $\frac{2}{3} n^3 = 1152$) clearly favors elimination over cofactors.

Another approach requiring $\frac{4}{3} n^3 + O(n^2)$ work would be reducing $Q$ to tridiagonal form with Householder transformations, which also puts $12I - Q$ into tridiagonal form. Computing $\det(Q)$ and $\det(12I - Q - J)$ can thereafter be done in $O(n)$ operations. [The effect of the rank one update $-J$ in the second determinant can be expressed as a scalar factor given by solving one tridiagonal system.]

Implementing such an independent computation might be worthwhile as a check on the results of successful (or failed) calls to Armadillo's det function.