Pitch detection algorithm for minsample size I am looking for a pitch detection algorithm that uses the least number of samples.

I don't care about the processing time. 

I hope to use this on audio signals.

I have tried using the one at the end of http://online.physics.uiuc.edu/courses/phys193/NSF_REU_Reports/2005_reu/Real-Time_Time-Domain_Pitch_Tracking_Using_Wavelets.pdf but the sample size to get a decent estimate is very high (maybe 4096 to lock a 440hz A note which is worse then my FFT)

Assuming super resolution I hope be predicting within +/- 2hz. So that a 440hz tone can register as no worse then 438hz.

Edited: super resolution range.
Consider trying an upsampled or interpolated ASDF, AMDF, autocorrelation or other similar periodicity estimation algorithm.

There in an information theoretic time versus frequency resolution versus noise trade-off.  At a sample rate of 44100, estimating 440 Hz +-2 Hz might require somewhere in the range of 2 to 6 times 44100/440 samples (to determine the existance of periodicity or pitch) up to 2.5 to 4 times 44100/2 samples (to separate 2 spectral lobes), depending on the S/N ratio, and whether that noise environment requires windowing, or allows sub-sample or sub-bin interpolation in your periodicity estimator and/or FFT.

BTW, "super resolution" for tuners is usually considered to be +-1 cent or better, even though this is below normal human audibility except for beating.