shway
/
Notepad
2
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
Notepad/enter/Machine Tips (Quantum)/Project Vault/Quantum Master's Paper/Sections/4c. Algorithms.md

6.2 KiB
Raw Permalink Blame History

"A computer without an algorithm is just a dumb machine." " The algoithms that computers is basically the method that a computer figures out how to get to its answer. Essentially it's like giving the brain to the body. The body exists now! Now time to bring it to life by setting up the algorithm which will connnect it all together.

  • Shor’s Algorithm: Shor's algorithm is a quantum computer algorithm for integer factorization. Informally, it solves the following problem: Given an integer, find its prime factors. It was invented in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer, Shor's algorithm runs in polynomial time. -search unordered list in square root n time rather than searching every element which leads to O(n)
    • The algorithm that quantum computers can effectively use to solve various problems that we have set up in society today. Essentially, our entire system is set up on mathematics; therefore, with this algorithm, a quantum computer can solve issues of factorization, discrete log, elliptical curve and more which means all RSA encrypted cryptosystems could easily be broken.
  • Grover Search Algorithm: Search algorithm that can produce amazing results for the unstructured search problem found in computer science. The classical 3-SAT NP problem can be solved with quantum computers with a significant speedup time. 
  • Selby’s algorithm → better than a d-wave quantum 
    • There are currently approximately 50 quantum algorithms in place to create a more quantum efficient system 
  • The Random Walk of the Markov Chain is used to find vertices on a graph 
    • However a quantum walk is able to improve their version of this 
    • The random walk/markov chain is used sampling/search problems in classical computing, whereas a quantum walk, where a simulated coherent quantum evolution of a particle moving on a graph is computed, would provide an alternate method to search that would outperform a markov chain of conditions, with both faster solution hitting and faster mixing. This had wide application in AI and machine learning improvements.

Resouces --> quantumalgorithmzoo.com

a = 7
factor_found = False
attempt = 0
while not factor_found:
    attempt += 1
    print("\nAttempt %i:" % attempt)
    phase = qpe_amod15(a) # Phase = s/r
    frac = Fraction(phase).limit_denominator(N) # Denominator should (hopefully!) tell us r
    r = frac.denominator
    print("Result: r = %i" % r)
    if phase != 0:
        # Guesses for factors are gcd(x^{r/2} ±1 , 15)
        guesses = [gcd(a**(r//2)-1, N), gcd(a**(r//2)+1, N)]
        print("Guessed Factors: %i and %i" % (guesses[0], guesses[1]))
        for guess in guesses:
            if guess not in [1,N] and (N % guess) == 0: # Check to see if guess is a factor
                print("*** Non-trivial factor found: %i ***" % guess)
                factor_found = True

A quantum circuit is a graphic representation of a quantum algorithm

The circuit shows that the output of the measurement of the qubit, whose state was |+〉, is 0 with probability 1/2 or 1 with the same probability. Fig. 2.2 shows the histogram of the 3 probability distribution generated in Qiskitwith two iterations.

For example, the sheer limit in the number of quantum computers is being tackled through quantum clouds, wher companies can provide software that allows users to access quantum computer time remotely. Another example is software that is able to compensate for high error rates in early generation quantum computers through highly specified and elaborate algorithms

Deutsch’s algorithm is the first algorithm exploiting quantum parallelism.

In the fina Section, we describe an implementation of Deutsch’s algorithm with only one qubit.

The Deutsch-Jozsa algorithm is a deterministic quantum algorithm, a generalization of Deutsch’s algorithm, and the first example that is exponentially faster than its equivalent classical deterministic algorithm.

the first deterministic quantum algorithm with linear gain over the best deterministic or randomized classical algorithm

It is a quantum algorithm exponentially faster than the best deterministic or randomized equivalent classical algorithm. It is a remarkable bu underestimated scientific contribution to quantum computing. Simon’s algorithm exploits not only quantum parallelism but also maximal entanglement.

In oracle-based algorithms, the oracle is not implemented by us—it is implemented by someone else. However, it is important to know how it is done in order to understand the whole process.

It describes two quantum algorithms for integer factoring and discrete logarithm that run in polynomial time. The best-known classical algorithm run in sub-exponential time. Shor’s algorithms exploit not only quantum parallelism but also entanglement, being a remarkable and celebrated scientific contribution to quantum comput ing

Quantum algorithm is a subarea of quantum computing that is evolving quickly not only in term of new algorithms but also in terms of applications and implementations. The basic algorithm are the pillars of this new edifice. The construction started with a change in the rules of th game. Instead of storing information in bits, which take either zero or one, we are allowed to store information in qubits, the state of which is a superposition of zeroes and ones. The rule based on classical mechanics were replaced by rules based on quantum mechanics