Methods, systems, and apparatus for quantum phase estimation. In one aspect, an apparatus includes a quantum circuit comprising a first quantum register comprising at least one ancilla qubit, quantum gates, comprising at least (i) two Hadamard gates, (ii) a phase gate, (iii) a unitary operator, and (iv) a measurement operator, a second quantum register comprising one or more qubits, wherein the second quantum register is prepared in an arbitrary quantum state that is not an eigenstate of the unitary operator; and a phase learning system, configured to perform phase estimation experiments on the quantum circuit, comprising repeatedly measuring the state of an ancilla qubit for each phase estimation experiment to determine an expectation value of the state of the ancilla qubit and learn phases of the eigenvalues of the unitary operator.