Question: Given a unitary matrix acting on $n$ qubits, can we find the shortest sequence of Clifford + T gates that correspond to that unitary?
For background on the question, two important references:
Getting an optimal decomposition is definitely an open problem. (And, of course, the decomposition is intractable, $\exp(n)$ gates for large $n$.) A "simpler" question you might ask first is what is the shortest sequence of cnots and single qubit rotations by any angle, (what IBM, Rigetti, and soon Google currently offer, this universal basis of gates can be expressed in terms of your basis of Cliffords and t-gates). This "simpler" question is also open and has a non-unique answer. A related question is what is an exact optimal decomposition of gates from a universal basis to go from ground state to a given final state.
I am assuming you are referring to exact decompositions. If you want approximate decompositions, there are different methods for that, such as the Trotter-Suzuki decomposition, or approximating an exact decomposition.
The "quantum csd compiler" in Qubiter does a non-optimized decomposition of any n qubit unitary into cnots and single qubit rots using the famous csd (Cosine-Sine Decomposition) subroutine from LAPACK. Some enterprising person could try to find optimizations for Qubiter's quantum compiler. You can use Qubiter's compiler, for example (I wrote a paper on this), to let your classical computer re-discover Coppersmith's quantum Fourier Transform decomposition!
Qubiter is open source and available at github (full disclosure - I wrote it).
Suppose that an exact synthesis was possible for your provided unitary (the number of theoretic restriction on the entries) and so the algorithms described in the question gave you a sequence of Clifford+T gates that implemented that unitary. As stated in the Giles-Selinger paper, you get a sequence that is very far from optimal. So at this point you have reduced to the word problem in the group generated by the Clifford+T gate set. Some groups have algorithms to shorten a given word while still representing the same element of the group into a normal form that is the shortest within that class. Others do not.
More details to illustrate the principle: Let us say there are $2$ qubits. Denote $S_1$ etc for the generator that does the phase gate on qubit $1$, $CNOT_{12}$ for $1$ being the control etc. Each one of these is treated as a letter. The algorithm will spit out some word in these generators. The group is the group with these generators and many relations like $S_i^4=1$ and $X_i Y_j = Y_j X_i$ when $i \neq j$ among many other relations. So this defines some finitely generated group. Because we have a word from the provided algorithms but has not been optimized, the task is to provide a convenient shortest possible normal form in the word problem for this group. So if given the word $S_1 S_1 S_2 S_1 S_1$ one could use the relation $S_1 S_2 = S_2 S_1$ twice and the $S_1^4=1$ relation once to get $S_2$ as a shorter word that represents the same group element. For a given group presentation, one would like an algorithm that takes an arbitrary word and reduces it. In general this is not possible.
Disclaimer for below: Forthcoming project/Haskell implementation joint w/ Jon Aytac.
I don't know about the solvability of the word problem for the Clifford+T gate set, but one can do something simpler with only the involutions (call them $r_i$) in that set and only the relations of the form $(r_i r_j)^{m_{ij}}=1$. That is a Coxeter group related to the Clifford+T gate set, but with an efficiently solvable word problem. So one may take the result of the Giles-Selinger algorithm and potentially shorten it using only these very simple relations (after looking at segments with only those involution letters). In fact any algorithm that takes a given unitary and approximates or exactly synthesizes it into Clifford+T can be fed into this procedure to potentially shorten it slightly.
