CLASSICAL AND QUANTUM COMPUTATIONAL METHOD AND APPARATUS FOR PERFORMING PRIME FACTORIZATION OF AN INTEGER, CLASSICAL AND QUANTUM COMPUTATIONAL METHOD AND APPARATUS FOR INVERTING A LOGIC GATE CIRCUIT

摘要

A quantum computational method of performing prime factorization of an integer includes determining a logic gate circuit including logic gates, the circuit configured to compute a multiplication function outputting the integer. The method includes determining gate-encoding Hamiltonians (HG) for each logic gate, each HG encodes an input-output relation of a logic gate and is a sum of summand Hamiltonians; providing a quantum system comprising constituents, wherein each summand Hamiltonian of each HG is associated with a constituent of the system; determining a first set of short-range quantum interactions of the constituents based on the logic gates; determining a second set of short-range quantum interactions of the constituents based on the integer; implementing the first and the second set of short-range quantum interactions; measuring at least a portion of the quantum system to obtain a read-out and determining a prime factor of the integer based on the read-out.