Его работа над квантовыми алгоритмами началась со статьи 1985 года, позже расширенной в 1992 году вместе с Ричардом Йозсой для создания алгоритма Дойча–Йозсы, одного из первых примеров квантового алгоритма, который экспоненциально быстрее любого возможного детерминированного классического алгоритма. В своей статье 1985 года он также предлагает использовать запутанные состояния и теорему Белла для квантового распределения ключей. При выдвижении его кандидатуры на избрание членом Королевского общества (FRS) в 2008 году его вклад был описан следующим образом:

[заложил] основы квантовой теории вычислений и впоследствии добился или участвовал во многих наиболее важных достижениях в этой области, включая открытие первых квантовых алгоритмов, теории квантовых логических элементов и квантовых вычислительных сетей, первой схемы квантовой коррекции ошибок и нескольких фундаментальных результатов квантовой универсальности. Он определил повестку дня всемирных исследовательских усилий в этой новой междисциплинарной области, добился прогресса в понимании ее философских последствий (с помощью варианта интерпретации множества вселенных) и сделал ее понятной широкой публике, особенно в своей книге “Ткань реальности”.

С 2012 года он работает над теорией конструкторов, попыткой обобщить квантовую теорию вычислений, чтобы охватить не только вычисления, но и все физические процессы. Вместе с Кьярой Марлетто в декабре 2014 года он опубликовал статью под названием Конструктивная теория информации, в которой высказывается предположение, что информация может быть выражена исключительно в терминах того, какие преобразования физических систем возможны, а какие невозможны.