Η έρευνα του Aaronson επικεντρώνεται στις δυνατότητες και τα όρια των κβαντικών υπολογιστών και γενικότερα στην υπολογιστική πολυπλοκότητα και τη σχέση της με τη φυσική. Στο πλαίσιο της συνεργασίας It from Qubit, ο Aaronson ενδιαφέρεται εξαιρετικά για την αλληλεπίδραση μεταξύ της υπολογιστικής πολυπλοκότητας και της κβαντικής βαρύτητας. Αυτό περιλάμβανε τη μελέτη των πτυχών της επιστήμης των υπολογιστών του επιχειρήματος Harlow-Hayden, το οποίο επιχειρεί να εφαρμόσει τη θεωρία πολυπλοκότητας στο περιβόητο «παράδοξο τείχους προστασίας» στις πληροφορίες για τις μαύρες τρύπες, καθώς και τη συνεργασία με τον Leonard Susskind για την κατανόηση της ανάπτυξης της πολυπλοκότητας των κβαντικών κυκλωμάτων σε συστήματα που προκύπτουν από την αλληλογραφία AdS/CFT.