I think the best way to answer your question, is to ask yourself the same question, but replace "Test::Deep" with some other module name that isn't strictly neccessary for the basic functionality of the packge, but may be usefull to install.

If you're willing to put in the extra effort to make your distribution behave correction either way, then don't make it a PRE_REQ. But if it won't function entirely correctly without it, then you should most certainly require it.

Which raises the question: do you consider the tests that use Test::Deep neccessary in order for the entire test suite to "function entirely correctly" ?