A lógica de um computador quântico é completamente diferente!
Primeiro, toda função usada em um computador quântico deve ser reversível, ou seja, com a saída deve ser possível gerar novamente a entrada. A maioria dos algoritmos dos computadores convencionais já quebram essa regra. Por exemplo a adição não é reversível! Se você somar 2+7 vai dar 9, mas é impossível fazer uma função que pegue 9 e retorne 2 + 7, pois um pouco da informação foi perdida no processo.
Assim as operações de adição, subtração, multiplicação e divisão convencionais não são possíveis em um computador quântico. Com essa restrição também se chega que qualquer função quântica deve ter o mesmo número de bits de entrada e de bits de saída. Isso não é uma limitação, pois métodos reversíveis existem para todos as funções computáveis, porém requer uma maneira diferente de pensar na resolução de um problema.
Outra propriedade bem diferente é que, no meio de um programa quântico nenhum bit pode ser modificado, copiado ou deletado. Uma operação deste tipo iria "estragar" os bits! Além disso, em uma função quântica não podem existir loops, nem ifs, nem nenhum tipo de controle convencional de fluxo: uma operação é executada depois da outra de forma sequencial. E as operações quânticas alteram todos os bits de uma vez de uma forma que seriam necessárias muitas operações normais para faze-lo, formando um novo conjunto de instruções básicas que é muito mais eficiente para alguns tipos de problemas.
Se o computador quântico começar a ser viável, a ideia mais aceita é que a programação continuará da mesma forma, porém com funções quânticas! Um computador convencional vai escrever os bits de entrada na memória de um computador quântico e dar um sinal para ele iniciar a função. Depois que o resultado está calculado é só ler os valores de saída. Imagino que vá existir uma biblioteca de funções quânticas para se usar no código e isso deve ficar transparente para o programador.
O computador quântico é extremamente rápido para se fazer uma transformada discreta de Fourier resolvendo ela com complexidade O(n^2). Em um computador convencional essa operação tem complexidade O(n*2^n), muito maior. Daí, em 1994 um matemático chamado Peter Shor fez um algoritmo quântico com complexidade O(n^3) para fatorar um número utilizando a transformada quântica de Fourier. Depois disso o interesse nos computadores quânticos cresceu muito, pois fatorar um número com essa velocidade conseguiria quebrar muitos dos sistemas de criptografia atuais.
Tentei falar o mais importante, é muito difícil explicar isso tentando ser o mais básico possível! Uma discussão mais detalhada pode facilmente chegar em filosofia existencial profunda e na estranheza do universo, o que não iria ajudar muito a responder a pergunta :)