  The use of quantum processing units (QPUs) promises speed-ups for solving
computational problems. Yet, current devices are limited by the number of
qubits and suffer from significant imperfections, which prevents achieving
quantum advantage. To step towards practical utility, one approach is to apply
hardware-software co-design methods. This can involve tailoring problem
formulations and algorithms to the quantum execution environment, but also
entails the possibility of adapting physical properties of the QPU to specific
applications. In this work, we follow the latter path, and investigate how key
figures - circuit depth and gate count - required to solve four cornerstone
NP-complete problems vary with tailored hardware properties. Our results reveal
that achieving near-optimal performance and properties does not necessarily
require optimal quantum hardware, but can be satisfied with much simpler
structures that can potentially be realised for many hardware approaches. Using
statistical analysis techniques, we additionally identify an underlying general
model that applies to all subject problems. This suggests that our results may
be universally applicable to other algorithms and problem domains, and tailored
QPUs can find utility outside their initially envisaged problem domains. The
substantial possible improvements nonetheless highlight the importance of QPU
tailoring to progress towards practical deployment and scalability of quantum
software.
