This is very much an open question, but yes, there is a considerable amount of work that is being done on this front.
It is, first of all, to be noted that there are two major ways to merge machine learning (and deep learning in particular) with quantum mechanics/quantum computing:
1) ML $\to$ QM
Apply classical machine learning techniques to tackle problems arising in the context of quantum mechanics/quantum information/quantum computation.
This area is growing too fast for me to even attempt a decent list of references, so I will just link to a couple of the most recent works in this direction: in 1803.04114 the authors used a machine learning approach to find circuits to compute the overlap between two states (there are a number of other works in this same direction), and in 1803.05193 the authors studied how deep neural networks can be used to find quantum control correction schemes.
2) QM $\to$ ML
Study of quantum algorithms to analyze big data, which often amounts to look for "quantum generalizations" of classical machine learning algorithms. You can have a look at this other answer of mine to get some basic references about this topic.
More specifically for the case of deep learning, in 1412.3489 (aptly named Quantum Deep Learning) the authors propose a method (effectively, a quantum algorithm) to generally speed-up the training of deep, restricted Boltzmann machines.
Another relevant reference here is 1712.05304, in which the authors develop a low-depth quantum algorithm to train quantum Boltzmann machines.
See 1708.09757, as well as the references in the linked answer, to find many more works on this. Note that the speed-up that is claimed in these works can vary wildly, from exponential speed-ups to polynomial ones.
Sometimes the speed-up comes from the use of quantum algorithms to solve particular linear algebraic problems (see e.g. Table 1 in (1707.08561), sometimes it comes from what basically amounts to the use of (variations of) Grover's search, and sometimes from other things (but mostly these two).
Quoting from Dunjko and Briegel here:
The ideas for quantum-enhancements for ML can roughly be classified
into two groups: a) approaches which rely on Grover’s search and
amplitude amplification to obtain up-to-quadratic speed-ups, and, b)
approaches which encode relevant information into quantum amplitudes,
and which have a potential for even exponential improvements. The
second group of approaches forms perhaps the most developed research
line in quantum ML, and collects a plethora quantum tools – most
notably quantum linear algebra, utilized in quantum ML proposals.
More direct answer to the three questions
Having said the above, let me more directly answer the three points you raised:
Could a deep learning algorithm run on a quantum computer? Most definitely yes: if you can run something on a classical computer you can do it on quantum computers. However, the question one should be asking is rather can a quantum (deep) machine learning algorithm be more efficient than the classical counterparts? The answer to this question is trickier. Possibly yes, there are many proposals in this direction, but it is too soon to say what will or will not work.
Does it make sense to try? Yes!
- Are there other quantum algorithms that would make deep learning irrelevant? This strongly depends on what you mean by "irrelevant". I mean, for what is known at the moment, there may very well be classical algorithms that will make deep learning "irrelevant".