A method for a quantum computer to determine a nearest neighbor vector to a target vector representing a target data point represented as a quantum state by performing a quantum computation to obtain an estimate of a distance between the target vector and each data vector from a set of data vectors wherein each data vector of the set of data vectors represents a data point and is represented as a quantum state, wherein a quantum distance estimate procedure is selected from a set of quantum distance estimate procedures based on distance type wherein the distance type is a Euclidean distance or an inner product and the quantum distance estimation procedure is selected to obtain a distance estimate for a Euclidean distance or an inner product, the method performed by the quantum computer, comprising for each data vector represented as a quantum state from the set of data vectors: for each of a number, k, of votes associated with a majority voting scheme, applying the selected quantum distance estimation procedure to the quantum state representing the target vector and the quantum state representing the data vector to obtain a distance between the quantum state representing the target vector and the quantum state representing the data vector wherein the selected quantum distance estimate procedure implements a quantum distance operator; applying amplitude estimation without measurement to the quantum state obtained from applying the selected quantum distance estimate procedure to the quantum state representing the target vector and the quantum state representing the data vector, using a quantum register with a size, R, proportional to the inverse of a specified error tolerance, 1/ ε, and wherein the amplitude estimation provides a quantum state that is a superposition of a first quantum state representing the correct distance estimate and a second quantum state corresponding to a quantum superposition of incorrect distance estimates; and storing a result for the distance estimate as the quantum state associated with said each vote, wherein said quantum state comprises the superposition of the first quantum state associated with said each vote representing the correct distance estimate and the second quantum state corresponding to the quantum superposition of incorrect distance estimates returned by the amplitude estimation without measurement; and selecting a median distance based on the quantum states associated with the k votes corresponding to the median value of the distance estimates; and the method further comprises: determining the nearest neighbor vector as being a vector of the set of data vectors associated with a minimum of the selected median distances between the quantum state representing the target vector and the quantum states representing each vector of the set of data vectors and outputting an estimate of the minimum selected median distance using a Dürr-Høyer minimization procedure with a Grover search. applying the selected quantum distance estimation procedure to the quantum state representing the target vector and the quantum state representing the data vector to obtain a distance between the quantum state representing the target vector and the quantum state representing the data vector wherein the selected quantum distance estimate procedure implements a quantum distance operator; applying amplitude estimation without measurement to the quantum state obtained from applying the selected quantum distance estimate procedure to the quantum state representing the target vector and the quantum state representing the data vector, using a quantum register with a size, R, proportional to the inverse of a specified error tolerance, 1/ ε, and wherein the amplitude estimation provides a quantum state that is a superposition of a first quantum state representing the correct distance estimate and a second quantum state corresponding to a quantum superposition of incorrect distance estimates; and storing a result for the distance estimate as the quantum state associated with said each vote, wherein said quantum state comprises the superposition of the first quantum state associated with said each vote representing the correct distance estimate and the second quantum state corresponding to the quantum superposition of incorrect distance estimates returned by the amplitude estimation without measurement; and selecting a median distance based on the quantum states associated with the k votes corresponding to the median value of the distance estimates; and the method further comprises: determining the nearest neighbor vector as being a vector of the set of data vectors associated with a minimum of the selected median distances between the quantum state representing the target vector and the quantum states representing each vector of the set of data vectors and outputting an estimate of the minimum selected median distance using a Dürr-Høyer minimization procedure with a Grover search.