A phase estimation method (200, 400) of estimating an eigenvalue gap in a target unitary using a computing environment comprising: a quantum computing environment comprising a quantum processing unit comprising at least one qubit and one or more measuring devices; and a classical computing environment comprising a classical processor, the method comprising repeating multiple times the steps of: preparing the at least one qubit of the quantum processing unit in an initial quantum state; applying (208, 402) a random unitary to the initial quantum state of the at least one qubit in the quantum processing unit to produce a random quantum state, the random unitary being selected from a set of random unitaries, wherein a different random unitary is drawn each time the steps are repeated such that the random unitaries are drawn uniformly according to a Haar measure; evolving (210, 404) the random quantum state of the at least one qubit in the quantum processing unit based on a target unitary; applying (212, 406) an inverse of the random unitary to the evolved quantum state of the at least one qubit in the quantum processing unit to produce a final quantum state; measuring the final quantum state of the at least one qubit in the quantum processing unit using the one or more measuring devices; and producing, using the classical processor, an estimate of an eigenvalue gap of the target unitary using Bayesian inference based on a Haar average of the measurements of the final quantum state with respect to the initial quantum state. a quantum computing environment comprising a quantum processing unit comprising at least one qubit and one or more measuring devices; and a classical computing environment comprising a classical processor, the method comprising repeating multiple times the steps of: preparing the at least one qubit of the quantum processing unit in an initial quantum state; applying (208, 402) a random unitary to the initial quantum state of the at least one qubit in the quantum processing unit to produce a random quantum state, the random unitary being selected from a set of random unitaries, wherein a different random unitary is drawn each time the steps are repeated such that the random unitaries are drawn uniformly according to a Haar measure; evolving (210, 404) the random quantum state of the at least one qubit in the quantum processing unit based on a target unitary; applying (212, 406) an inverse of the random unitary to the evolved quantum state of the at least one qubit in the quantum processing unit to produce a final quantum state; measuring the final quantum state of the at least one qubit in the quantum processing unit using the one or more measuring devices; and producing, using the classical processor, an estimate of an eigenvalue gap of the target unitary using Bayesian inference based on a Haar average of the measurements of the final quantum state with respect to the initial quantum state. preparing the at least one qubit of the quantum processing unit in an initial quantum state; applying (208, 402) a random unitary to the initial quantum state of the at least one qubit in the quantum processing unit to produce a random quantum state, the random unitary being selected from a set of random unitaries, wherein a different random unitary is drawn each time the steps are repeated such that the random unitaries are drawn uniformly according to a Haar measure; evolving (210, 404) the random quantum state of the at least one qubit in the quantum processing unit based on a target unitary; applying (212, 406) an inverse of the random unitary to the evolved quantum state of the at least one qubit in the quantum processing unit to produce a final quantum state; measuring the final quantum state of the at least one qubit in the quantum processing unit using the one or more measuring devices; and producing, using the classical processor, an estimate of an eigenvalue gap of the target unitary using Bayesian inference based on a Haar average of the measurements of the final quantum state with respect to the initial quantum state.