Messaggi di Rogue Scholar

language
MatematicaInglese
Pubblicato in Math ∩ Programming
Autore Jeremy Kun

Problem: Given a massive data stream of $ n$ values in $ \ 1, 2, \dots, m \$ and the guarantee that one value occurs more than $ n/2$ times in the stream, determine exactly which value does so. Solution: (in Python) def majority(stream): held = next(stream) counter = 1 for item in stream: if item == held: counter += 1 elif counter == 0: held = item counter = 1 else: counter -= 1 return held Discussion: Let’s prove correctness.

MatematicaInglese
Pubblicato in Math ∩ Programming
Autore Jeremy Kun

Or how to detect and correct errors Last time we made a quick tour through the main theorems of Claude Shannon, which essentially solved the following two problems about communicating over a digital channel. What is the best encoding for information when you are guaranteed that your communication channel is error free? Are there any encoding schemes that can recover from random noise introduced during transmission?

MatematicaInglese
Pubblicato in Math ∩ Programming
Autore Jeremy Kun

There are two basic problems in information theory that are very easy to explain. Two people, Alice and Bob, want to communicate over a digital channel over some long period of time, and they know the probability that certain messages will be sent ahead of time. For example, English language sentences are more likely than gibberish, and “Hi” is much more likely than “asphyxiation.” The problems are: Say communication is very expensive.

MatematicaInglese
Pubblicato in Math ∩ Programming
Autore Jeremy Kun

Last time we left off with the tantalizing question: how do you do a quantum “AND” operation on two qubits? In this post we’ll see why the tensor product is the natural mathematical way to represent the joint state of multiple qubits. Then we’ll define some basic quantum gates, and present the definition of a quantum circuit.

MatematicaInglese
Pubblicato in Math ∩ Programming
Autore Jeremy Kun

The best place to start our journey through quantum computing is to recall how classical computing works and try to extend it. Since our final quantum computing model will be a circuit model, we should informally discuss circuits first. A circuit has three parts: the “inputs,” which are bits (either zero or one); the “gates,” which represent the lowest-level computations we perform on bits;

MatematicaInglese
Pubblicato in Math ∩ Programming
Autore Jeremy Kun

Quantum mechanics is one of the leading scientific theories describing the rules that govern the universe. It’s discovery and formulation was one of the most important revolutions in the history of mankind, contributing in no small part to the invention of the transistor and the laser. Here at Math ∩ Programming we don’t put too much emphasis on physics or engineering, so it might seem curious to study quantum physics.

MatematicaInglese
Pubblicato in Math ∩ Programming
Autore Jeremy Kun

Problem: Alice chooses a secret polynomial $ p(x)$ with nonnegative integer coefficients. Bob wants to discover this polynomial by querying Alice for the value of $ p(x)$ for some integer $ x$ of Bob’s choice. What is the minimal number of queries Bob needs to determine $ p(x)$ exactly? Solution: Two queries. The first is $ p(1)$, and if we call $ N = p(1) + 1$, then the second query is $ p(N)$.