Combining Hard and Soft Constraints in Quantum Constraint-Satisfaction Systems
This work presents a generalization of NchooseK, a constraint satisfaction system designed to target both quantum circuit devices and quantum annealing devices. Previously, NchooseK supported only hard constraints, which made it suitable for expressing problems in NP (e.g., 3-SAT) but not NP-hard problems (e.g., minimum vertex cover). In this paper we show how support for soft constraints can be added to the model and implementation, broadening the classes of problems that can be expressed elegantly in NchooseK without sacrificing portability across different quantum devices.
Through a set of examples, we argue that this enhanced version of NchooseK enables problems to be expressed in a more concise, less error-prone manner than if these problems were encoded manually for quantum execution. We include an empirical evaluation of performance, scalability, and fidelity on both a large IBM Q system and a large D-Wave system.
Ellis Wilson is currently a 4th year computer science PhD student at North Carolina State University working with Frank Mueller. He received his Bachelor in Science in engineering physics with a focus in scientific computing from the University Wisconsin-Madison, where he worked with the Computational Nuclear Engineering Research Group under Paul Wilson. His current focus is on quantum computing, and he is approaching it from the software angle; he has investigated subjects such as self-error measurement before transpilation, circuit approximations, and his current work, NchooseK. NchooseK is a domain specific language being developed jointly with Scott Pakin from Los Alamos National Lab, where Ellis has interned for two summers now.
--- Co-hosted with IBM Quantum Hub at NC State University and Kenan Institute of Private Enterprise at UNC Kenan-Flagler Business School.