Linha de Produção de qPhones

A Sociedade Brasileira de Celulares (SBC) está desenvolvendo um novo modelo de smartphones que utiliza computação quântica, os qPhones. Diferente dos aparelhos tradicionais, que armazenam bits, essa nova arquitetura utilizará qubits.

Um qubit (quantum bit) é a unidade básica da informação quântica, assim como o bit na computação clássica. Porém, enquanto que um bit clássico assume apenas um estado por vez (0 ou 1), um qubit pode existir em superposição, assumindo múltiplos estados simultaneamente como uma mistura quântica de 0 e 1, cada um com uma probabilidade de ser medida ao ser observado.

Deste modo, caso um dispositivo consiga armazenar qubits, todas as suas combinações podem ser representadas simultaneamente, por conta da superposição. Por exemplo, se um dispositivo armazena 3 qubits, podemos ter a representação de $2^3=8$ estados clássicos superpostos, sendo eles 000, 001, 010, 011, 100, 101, 110 e 111.

Na prática, podemos assumir que para simular um $1$ qubit precisamos de $2$ bits, para simular $2$ qubits precisamos de $4$ bits, para simular $3$ qubits precisamos de $8$ bits, e assim por diante. Assim, para simular completamente a memória de um celular clássico com $M$ megabytes (MB), os engenheiros da SBC precisam garantir que os qubits do novo aparelho sejam capazes de representar ao menos os $M$ megabytes. Considere que $1$ MB é equivalente a $10^6$ bytes.

Você foi recentemente contratado pela SBC para ajudar na linha de produção dos novos smartphones quânticos. Sua tarefa é, dado o valor de memória de $M$ megabytes, determinar o número mínimo de qubits necessários para simular todos os estados possíveis de um dispositivo clássico com essa quantidade de memória.

Um inteiro $M$ ($1 \le M \le 10^{10}$) representando a quantidade de memória em MB de um dispositivo tradicional.

Um inteiro representando o número mínimo de qubits necessários para simular todos os estados possíveis de um dispositivo clássico com $M$ megabytes de memória.