You misrepresent Penrose's argument. He certainly doesn't claim that we 'think by logical deduction' (although obviously we can), quite the opposite. He points out that if (as some strong AI proponents claim) the mind is simply an algorithmic process, equivalent to a Turing machine, it would be impossible for us to understand Gödel's incompleteness theorem, which we (some of us, anyway) clearly do. Therefore, the mind cannot be completely equivalent to an algorithm, no matter how complex.
He speculates that some type of quantum process could be involved, though he freely admits that he can't demonstrate a physical mechanism that would operate at body temperature ('more research is needed into this topic') - perhaps the work examined by the authors is taking us closer to establishing the feasibility of such a process.