applying quantum and hybrid algorithms

Quantum cryptography leverages the principles of quantum mechanics to provide theoretically unbreakable encryption. Quantum computers rely on the law of superposition where a particle can exist in multiple states simultaneously, as opposed to classical theory where we know the exact value of a particle.

Classical cryptography is essential for securing information. We use it everyday in blockchain technology, sending encrypted messages, sending web requests between a client and a server. It’s generally quite secure as classical algorithms such as RSA or elliptic curve, are extremely difficult to break. Can quantum algorithms break classical ones? technically yes, are quantum computers a threat right now? no, probably not.

what is the difference between classical and quantum cryptography?

Classical cryptography is secured through algorithms, that are near impossible for a human to solve and take massive computing resources for a machine to break. For example, the RSA digital signature algorithm that relies on the difficulty of factoring large numbers. I have a blog post on RSA, but the result of the algorithm is a 2048-bit number which is incredibly difficult to factorize, impossible for an individual to factorize and would take an insane amount of resources for a computer to factorize.

for reference, try factorizing a smaller number 221, it’s going to take a while to do in your head but if you test the possible combinations on a calculator, you’re left with 11 and 17. There’s not really any algorithm to factorize a number. If we take a slightly bigger number, say 108215369161 a 12 bit number and try find the prime factors, its going to be a bit more diffcult, actually pretty difficult. You would find the two integers 123457 and 876543. now imagine this on a much larger scale. If its hard to imagine how much larger a scale there are 2^82 atoms in the universe the size of a 2048-bit number used to secure rsa is 2 x 10^2047.

In comparison, Quantum cryptography uses the laws of quantum physics, specifically the principle that any attempt to measure or intercept a quantum state alters it. This means any attempt to break quantum algorithms or listen in on information will be detected.

Quantum computing relies on the law of superposition which does not exist in classical computing/physics. Where, until measured, a particle can exist in multiple states simultaneously. The state of a quantum particle does not exist in a single state until measured. Superposition has been proven through the double-slit experiment and states that when two or more waves are combined the result is the sum of the individual waves.

superposition states that when two or more waves are combined the resulting state is the sum of the two waves. We can apply the same concept to particles where a particle is in a superposition of multple states we can add the wave functions together to result in a state that represents the superposition. Its difficult to explain quantum cryptography in the same terms as classical without it just coming off as linear algebra

is quantum cryptography a threat to classical cryptography?

Yes and no. We have discussed classical asymmetric cryptography such as RSA in this blog as well as popular hashes such as SHA-256. Quantum cryptography cannot break classical hashes. why? symmetric encryption goes one way, its a hash, a jumble of numbers without a stable home route. Asymmetric encryption on the other hand, is meant to be decrypted by whoever is authorized to decrypt it.

Lets talk about how classical computers think compared to quantum computers. We know that computers think in binary digits; zeros and ones and known as bits (digital bytes). Quantum computers think in qubits (quantum digital bytes) and the main difference between a bit and quibit is the logic of its state. A bit is absolutely a zero or a one while a quibit is in a superposition of zero and one, not that its one or the other but it exists in multiple states as multiple realities at once.

bloc sphere or the geometric representation of a qubit in a superposition of multiple states

One algorithm, discovered by Peter Shor in 1994, also known as Shor’s algorithm, finds the logarithmic inverse of a

shor’s algorithm, classical reduction and quantum explanation.

Shor’s algorithm uses a quantum algorithm to find the prime factors of an interger. It’s difficult to explain Shor’s algorithm properly without just describing linear algebra. The scientific notation for Shor’s algorithm is described as

If you think about factoring an interger through classical cryptography, where N is our integer and p and q are our prime factors technically we could find factors of our integer that are not prime numbers and factorise them until just p and q remain. This is known as the Euclidean algorithm which calculates the GCD (greatest common divisor). A simple example of this would be where N=10002 where N is an even number so we know it’s divisible by 2 so p=2 and we know when we divide N by p we are left with q=5001.

Ok, now lets assume N is not an even number. How would we find it’s integer factors? We can choose an integer a that is comprime to N and compute the modulo and find the smallest possible integer r so a^r = 1 (mod N). If r is even and a^(r/2) = 1 (mod N) then we know that N can be factored using the greatest common divisor of a^(r/2) = 1 and N. If not, choose a new number a and repeat the process.

The goal of this algorithm is, essentially, to find the order r of a modulo N which is also the smallest possible integer, should be equivalent to a^r = 1 (mod N). To achieve this on a quantum computer, the algorithm prepares a quantum circuit involving two registers, the first to store the value of x. this register determines how accurate of an approximation the circuit produces, we describe the first register with the notation 2n+1 where n is the number of bits required to represent N, the second register has n qubits where n is the same as defined for the first register.

The first register is initialized to the state |0 and the second to state |1. Hadamard Gates are applied to each qubit in the first register to create a superposition of all states, |0 and |1. Hadamard gates are essentially quantum gates that transform the computational states |0 and |1 into superposition. Hadamard gates are a type of quantum gate used to manipulate the state of a qubit for a quantum circuit. because a qubit exists in a superposition of multiple states, a quantum gate can perform multiple operations simultaneously.

diagram showing basic quantum gates and their matrix representations. 

The types of operations quantum gates perform include; rotation where rotation gates are used to rotate the state of a quibit around an x,y, and z axis. Phase shift gates that shift the state of a qubit by a certain amount. The third type of quantum gates are measurement gates which measure the state of a quibit by collapsing it. Quantum gates are essential for applying shor’s algorithm and factoring large numbers. Quantum gates perform the operation |x⟩ ⊗ |1⟩ → |x⟩ ⊗ |a^x mod N which means the value of a^x mod is stored in the second register while the value of the first stays the same. essentially for each value of x in superposition the gate calculates a^x mod N and stores the value in the second register. We can measure the first register which should result in a multiple of N/r where r is the period of the function a^x mod N.

hybrid variational quantum eigensolver (h-vqe)

where do we apply hybrid quantum algorithms? H-VQE is generally used for quantum chemistry, quantum simulations, and optimization problems. It is called a hybrid algorithm as it combines classical and quantum computing techniques.

H-VQE is a variation of the Eigansolver algorithm. Eignsolver algorithm is a classical algorithm used to find eigenvectors and eigenvalues of a matrix, which generally involves directly solving the eiganvalue equation H|ψ⟩ = E|ψ⟩. Where H represents the Hamiltonian operator which corresponds to the total energy of a system, |ψ⟩ stands for the quantum state vector or can be referred to as the possible state of a system or can be known as a ket. E is the The quantum variation was introduced in 2014 in a paper by Alberto Peruzzo and is based off of earlier quantum work including QAOA (quantum approximate optimization algorithm).

We can describe the architecture of H-VQE using the below diagram. The first block, Quantum state preparation, prepares the quantum state based off the input parameters. We discussed quantum gates above, parameters for the quantum state preparation involves angles that control the rotation gates applied to qubits.

The quantum modules compute the prepared quantum states. They compute the hamiltonian value (H) or the total energy of the system. The classical adder computes via CPU which you are probably more familiar with. This step provides a classical visual of quantum computation.

After classical adder, a classical minimization algorithm takes place on the CPU, it takes the expectation value of the hamiltonian value and determines the new state parameters that minimise the energy of the system. The classical feedback decision updates parameters which prepares new quantum states based on the new parameters.

workflow of quantum variational Eigensolver

quantum algorithms vs blockchain techology

Probably one of the most common conversations when it comes to quantum computing and algorithms is blockchain technology. Can quantum computers break everyone’s crypto wallets? technically yes, it is very unlikely that someone is going to steal your crypto currency in the near future though.

How is blockchain technology vulnerable to quantum algorithms?

First, lets look at the architecture of blockchain ledgers. A block within a ledger is identified via several components. The header used to identify which block in the blockchain. The previous block hash which connects them using the i+1th block to the 1th block using the previous block hash. The timestamp verifies the data on the block and creates a time and date of creation. The nonce is the block’s proof of work, and the merkel root is kind of like a digital fingerprint for the block.

Merkel Trees are essential for veifying the integrity of a block. It’s made up of all the hashes and transactions within the block, the root confirms all the facts in the tree. Merkel trees look like this

image from simplelearn

each node on the tree has its own cryptographic hash and the Merkel root is digitally signed with RSA encryption. We know that Shor’s algorithm can potentially break this digital signature by factorizing the 2048 bit number protecting it. While the leaves on a Merkel tree are cryptographic hash functions which arent really threatened by Shor’s algorithm, hashes are more at threat to Grover’s algorithm (but I will get into that later). The signature that verifies the Merkel tree is.