they are they just dont work in binary bits they work with qbits which simply have behavior rules diffrent from digital but can be simulated by one just inefficiently. much like a binary computer can be approximated by a balanced trianay computer or analog computer or by pumps valves and flowing water like in MONIAC. they are all turring complete and can simulate each other just not efficiently. they dont have any magical logic gates they are just able to do a task that would need require lot of time or many parrelel computaions or both in less time because a single qbit is in super position of 1 and 0 simaltaniously and we can do mathmatical operations on it without collapsing the superposition until we have observed it. to simulate this on a traditional computer you would need to run it for each 2 time per bit.

so for a 8 bit key for example you would need to run the same operation 256 times 65536 for a 16 bit key and 4,294,967,296 for a 32 bit. so in essence quantum computation just lets you cheat on massively parallel processes but is not a hyper-turring machine or a turring oracle. in fact there are many algorithms that you get no gain from using qubit other than i higher energy bill