An efficiency comparison of quantum variational and classical satisfiability algorithms for debugging combinational logic circuits
| dc.contributor.author | Demetriou, Peter | |
| dc.date.accessioned | 2022-12-19T12:54:28Z | |
| dc.date.available | 2022-12-19T12:54:28Z | |
| dc.date.issued | 2021 | |
| dc.description | A dissertation submitted to the Faculty of Engineering and the Built Environment, University of the Witwatersrand, Johannesburg in fulfilment of the requirements for the degree of Master of Science in Engineering. | |
| dc.description.abstract | This research presents an extension and contribution to combinational logic circuit debugging for future use in Very Large-Scale Integration system design. It also extends application of quantum computation to an engineering problem. Although previous work in this area has sped up approximate debugging solutions through the use of satisfiability solvers, the exact solutions become classically intractable as the number of gates in the system increases. Additionally, whilst many quantum algorithms show promise in solving classically intractable problems in theory, there have been few domain-specific implementations, particularly where hard and soft constraints exist, multiple solutions are required and noisy intermediate-scale quantum hardware is used. Two variational quantum algorithms are applied to a reduction of the satisfiability problem into a maximum independent set problem. While the Quantum Alternating Operator Ansatz approach constrains the optimisation to feasible solutions, the resulting ansatz is too large for current devices. A custom ansatz for a Variational Quantum Eigensolver along with a solution enumeration method is however able to make use of current hardware for the debugging problem. A small problem set is generated and solved using the aforementioned methods. The accuracy and complexity of the algorithms are benchmarked against an exact and approximate classical solver. The quantum approach outperforms the exact solver in both temporal and spatial scaling. With a theoretical mathematical result, it is argued that the quantum approach will likely outperform the approximate solver in the same way for future larger problems when quantum hardware size increases and becomes more robust to noise. | |
| dc.description.librarian | CK2022 | |
| dc.faculty | Faculty of Engineering and the Built Environment | |
| dc.identifier.uri | https://hdl.handle.net/10539/33833 | |
| dc.language.iso | en | |
| dc.title | An efficiency comparison of quantum variational and classical satisfiability algorithms for debugging combinational logic circuits | |
| dc.type | Thesis |