Zapata Computing, Inc.

Guoming Wang

Yudong Cao

Peter D Johnson

Pierre-Luc Dallaire-Demers

Enshan Dax Koh

A method and system are provided for solving combinatorial optimization problems. A classical algorithm provides an approximate or 'seed' solution which is then used by a quantum circuit to search its 'neighborhood' for higher-quality feasible solutions. A continuous-time quantum walk (CTQW) is implemented on a weighted, undirected graph that connects the feasible solutions. An iterative optimizer tunes the quantum circuit parameters to maximize the probability of obtaining high-quality solutions from the final state. The ansatz circuit design ensures that only feasible solutions are obtained from the measurement. The disclosed method solves constrained problems without modifying their cost functions, confines the evolution of the quantum state to the feasible subspace, and does not rely on efficient indexing of the feasible solutions as some previous methods require.

Classically-boosted quantum optimization

A hybrid quantum-classical (HQC) computer takes advantage of the available quantum coherence to maximally enhance the power of sampling on noisy quantum devices, reducing measurement number and runtime compared to VQE. The HQC computer derives inspiration from quantum metrology, phase estimation, and the more recent 'alpha-VQE' proposal, arriving at a general formulation that is robust to error and does not require ancilla qubits. The HQC computer uses the 'engineered likelihood function' (ELF) to carry out Bayesian inference. The ELF formalism enhances the quantum advantage in sampling as the physical hardware transitions from the regime of noisy intermediate-scale quantum computers into that of quantum error corrected ones. This technique speeds up a central component of many quantum algorithms, with applications including chemistry, materials, finance, and beyond.

Growing community of inventors

North York, Canada

Guoming Wang