Table of contents
Ji-hann H & John R
Yuhui Z
Linnaea R & Cortes B & Manusri V https://youtu.be/SSgXxrjysm0
Perhaps you found this course worthwhile; it was fun to teach.
If so, could you fill out the course survey; that helps me.
I'm available in the future, even after you leave RPI, to discuss any legal and ethical topic.
Table of contents
Connor McGowan writes,
I thought this seemed blog-worthy: https://interestingengineering.com/chinas-light-measuring-quantum-computer-captures-quantum-supremacy
A photon-based quantum computer in China just achieved quantum supremacy last week.
Course surveys are open. I open you've enjoyed this course. I worked hard to make it interesting and relevant. If you thought it worthwhile, could you please fill out the survey say so. That helps me a lot inside RPI. Very few students fill out the surveys, and so each response has an outsize weight.
Thanks.
Table of contents
David P
Connor M & Siddharth S
Justin C https://www.youtube.com/watch?v=h4yH9Kth_8k&feature=youtu.beview?usp=sharing
Joseph D
Cohen D
Amanda M
Connor G
Nik M & Nathanial P & Chace W & Ricardo D
Isaac P
Ji-hann H & John R
Yuhui Z
Linnaea R & Cortes B & Manusri V https://youtu.be/SSgXxrjysm0
Table of contents
This satisfies all late requests.
David P
Connor G & Siddharth S
Justin C https://www.youtube.com/watch?v=h4yH9Kth_8k&feature=youtu.be
Joseph D
Ricardo D
Cohen D
Amanda M
Connor M
Nik M
Nathanial P
Isaac P
Linnaea R & Cortes B & Manusri V
Ji-hann H & John R
Chace W
Yuhui Z
Prof Shi, Chemical and Biological Engineering, will tell us what he is doing in Ultrafast Nanoscale Optoelectronics, Investigating light matter interaction in low dimensional quantum materials. This is his web site.
If you liked this class, in Spring 2021, I am teaching ECSE-4740-01 APPL PARALLEL COMP FOR ENGRS. It will be completely virtual. Here is a poster.
Spin qubits | QuTech Academy 2018 10:30.
Operations on spin qubits | QuTech Academy 2018 13:44.
The transmon qubit | QuTech Academy 2018 6:03.
Two qubit gates | QuTech Academy 2018 5:30.
Qubit implementation in nanowire networks | QuTech Academy 2018 3:52.
Table of contents
We are fortunate that Prof Rena Huang will talk to us today. "Her current research activities focus on Si photonic devices and integration, on-chip slow-light waveguides, metastructure arrays, and high contrast gratings for applications in phased array antennas, optical neuromorphic computing, subwavelength imaging etc."
The four people who requested a specific date have it.
If anyone really hates the assigned day, then ask.
No one has been specific about teaming, which is optional. If you team up, mention your preferred dates, and I'll see.
David P Connor G Cortes B Justin C Joseph D Ricardo D
Cohen D Ji-hann H Amanda M Connor M Nik M Nathanial P Isaac P
John R Linnaea R Siddharth S Manusri V Chace W Yuhui Z
"Quantum Computing with Atoms and Optics" presented by Christopher Monroe, University of Maryland and IonQ, Inc., USA., 31:19, 2019 CLEO Plenary. CLEO®: Conference on Lasers and Electro-Optics® .
Moore has other excellent lectures online.
Due 2020-12-03 4:45pm in gradescope.
Write a page on the current progress in your project.
Total: 10 points.
Table of contents
If you have a preferred date, email me before Monday. I will make assignments then.
Homeworks up through 6 have been graded and published on gradescope. Your submissions were excellent.
If the semester ended today, everyone would get A- or A.
Prof Edwin Fohtung, The Fohtung Research Group, Materials Science and Engineering at RPI, will give a guest talk on his research interests in quantum computing.
H1: trapped ion.
10 qbits,
full connectivity,
can read isolated qbits in mid-computation,
hi-res rotations.
JP Morgan experimenting with it.
Honeywell Unveils Model H1, Quantum Computing As A Service, 3:00, 10/29/20.
Quantum Computer from Honeywell, 8:59, 6/22/20. Is Honeywell quantum computer the best performing?
Table of contents
guest speaker Edwin Fohtung WRF filling in remaining time for each class.
guest speaker Rena Huang
guest speaker Sufei Shi
student presentations
student presentations
student presentations
Because of the unexpected popularity of this class, there's no time for a second round of quick student presentations. Instead, work a little harder on the final project.
The final project may be done in teams of up to three students.
Deliverables:
Video presentation to class, in one of the last 3 class days.
Presentation length: 1 student - approx 12 min, 2 students: 15-20, 3: 20-30.
Eight page paper describing the project, written using the style of an IEEE or ACM journal or conference.
It will be due as a PDF file on Dec 11, the last class day.
Sign up by emailing me your team members and preferred dates (in preferred order if you care). It's helpful if the subject contains quantum.
QSI Seminar: Dr Marissa Giustina, Google Research, Building Google's Quantum Computer, 09/06/2020 55:52.
We'll continue at 10:00, if the network permits.
competitor to superconducting transmons (JJs).
Proponents say that it's better than transmon qbits.
What is an Ion Trap Quantum Computer? 2:30, 2/19/18.
founders from Maryland/College Park and Duke.
trapped ion
32 qbits.
low error rate
excellent quantum volume
will be available from Microsoft Azure and Amazon AWS Braket.
"To date, we’ve run single-qubit gates on a 79 ion chain, and complex algorithms on chains of up to 11 ions."
https://ionq.com/posts/october-01-2020-most-powerful-quantum-computer
Startup IonQ announces next-gen quantum computing system 1:49.
Minecraft, but on a Quantum Computer, 10:39, 10/17/20.
Due 2020-11-30 (2 weeks) 4:45pm in gradescope.
Teams of up to 3 are ok.
This project continues quantum computing on Amazon Braket .
10 points. Use actual D-Wave hardware.
Create or find a simple program. Run it.
Report the results.
Report your observations. Easy? Hard? Recommend to others? Not? Etc.
10 points. Repeat with actual IonQ or Rigetti hardware.
5 points. Compare them, to the extend reasonable given how different they are.
Total: 25. points.
Table of contents
Yesterday I gave a talk at an internal RPI biweekly meeting on quantum computing. See my talk
$ 1 Billion for Quantum Computing - Quantum Computing News 3:19, Sep 8, 2020.
Most Powerful Quantum Computer? - Quantum Computing News, 4:56, Oct 25, 2020.
QSI Seminar: Dr Marissa Giustina, Google Research, Building Google's Quantum Computer, 09/06/2020 55:52.
We'll watch some or all.
Prepared for RPI quantum seminar, 11/11/20
Table of contents
This page:
https://wrf.ecse.rpi.edu/Teaching/quantum-f2020/posts/quantum-summary.html
I've included lots of links for people who wish to explore further.
Alice laughed. "There's no use trying," she said: "one can't believe impossible things." "I daresay you haven't had much practice," said the Queen. "When I was your age, I always did it for half-an-hour a day. Why, sometimes I've believed as many as six impossible things before breakfast." - Through the Looking-Glass, and What Alice Found There (1871), by Lewis Carroll (Charles Lutwidge Dodgson).
While abstracting this summary from a large collection of disparate info, I might have made errors. However I believe this to be an unbiased and accurate summary.
I'm developing and teaching a new course that I proposed, ECSE-4964-01 Quantum Computer Programming.
19 students who seem to like it.
Several people in this meet are giving guest lectures (thanks!). Everyone here is welcome.
RPI paying me to learn (thanks!); however there's a lot I still don't know.
The WIRED Guide to Quantum Computing 08.24.2018. Nice non-too-technical summary of the history. The theory preceded the realization. This happens sometimes, e.g., with atomic energy. From there:
Physicist Paul Benioff suggests quantum mechanics could be used for computation.
Nobel-winning physicist Richard Feynman, at Caltech, coins the term quantum computer.
Physicist David Deutsch, at Oxford, maps out how a quantum computer would operate, a blueprint that underpins the nascent industry of today.
Mathematician Peter Shor, at Bell Labs, writes an algorithm that could tap a quantum computer’s power to break widely used forms of encryption.
D-Wave, a Canadian startup, announces a quantum computing chip it says can solve Sudoku puzzles, triggering years of debate over whether the company’s technology really works.
2013 Google teams up with NASA to fund a lab to try out D-Wave’s hardware.
Google hires the professor behind some of the best quantum computer hardware yet to lead its new quantum hardware lab.
IBM puts some of its prototype quantum processors on the internet for anyone to experiment with, saying programmers need to get ready to write quantum code.
Startup Rigetti opens its own quantum computer fabrication facility to build prototype hardware and compete with Google and IBM.
Feynman was the first to propose the theoretical idea of a quantum computer.
Richard Feynman - Quantum Mechanics 4:01.
Extracted from HD Feynman: FUN TO IMAGINE complete 1080p 1:06:49. Recorded in 1983.
A beginner's guide to quantum computing | Shohini Ghose https://www.youtube.com/watch?v=QuR969uMICM 10:04
Quantum Computing in Under 11 Minutes daytonellwanger https://www.youtube.com/watch?v=TAzZKAdX2Tw 10:56 more technical
https://towardsdatascience.com/introduction-to-quantum-programming-a19aa0b923a9?gi=69d861e26d80
https://medium.com/@jonathan_hui/qc-programming-with-quantum-gates-8996b667d256
https://medium.com/@jonathan_hui/qc-programming-with-quantum-gates-2-qubit-operator-871528d136db
https://www.cl.cam.ac.uk/teaching/0910/QuantComp/notes.pdf
They have a nice description of measurement starting at slide 10.
Each measurement operator has a basis vector set.
The operator represents the qbit as a linear combo of the basis vectors.
Then it projects the qbit onto one of the basis vectors, with probability being the length of that component.
It is possible for two different qbits to measure the same in some basis, but measure different in a different basis.
Which problems can quantum computers solve exponentially faster than classical computers? David Gosset, IBM quantum computing research scientist, explains why algorithms are key to finding out.
Can we make quantum technology work? | Leo Kouwenhoven | TEDxAmsterdam (18:19)
Experiment with Basic Quantum Algorithms (Ali Javadi-Abhari, ISCA 2018) (19:05)
Crazy counterintuitive idea that's the basis for quantum speedup.
Classical metaphor for entanglement:
Start with a piece of paper.
Tear it into two halves.
Put each half into an envelope, seal them, and mix them up, so that you can't tell which half is in which envelope.
Address and mail one envelope to a friend in Australia, and the other to a friend in Greenland.
When the Australian opens his envelope, he knows what the Greenlander will find in his.
However that doesn't let the Australian send any info to the Greenlander, or vv.
This has been demonstrated with real qbits transported 1000 miles apart.
Entanglement means that if you measure one qbit then what you observe restricts what would be observed when you measure the other qbit.
However that does not let you communicate.
Entanglement and superposition do funny things to operations. Consider the Controlled NOT gate. It has 2 inputs, x and y.
Classically, y is negated iff x=1. x doesn't change.
If x and y are superposed with a Hadamard basis, then y can affect x.
Cloning (copying) works in the classical world but not in the quantum world.
Classically, you can easily clone a bit. Consider a 2-bit system, $x, y$. Each bit can be 0 or 1. All 4 combos are possible. Represent the state with a 4-vector
$s=\begin{vmatrix} a_0\\a_1\\a_2\\a_3\end{vmatrix}$
where exactly one $a_i=1$ and the other three are 0. E.g., if $a_3=1$ then $x=y=1$.
Here's a 2-input, 2-output circuit that clones the first bit.
$x'=x\\y'=x$
Its truth table is
x y | x'y' 0 0 | 0 0 0 1 | 0 0 1 0 | 1 1 1 1 | 1 1
Represent the operation by a matrix multiplication on s. The matrix M is:
1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1
That is, the final state is $s'_i = \sum_j M_{ij} s_j$
However, M is singular. For quantum operations, M has to be unitary. So this is not a legal quantum circuit. Let's try again.
The better way is the 3-input Toffoli gate. The function is
$x'=x \\ y'=y \\ z'= z \oplus xy$
The truth table is
x y z | x'y'z' 0 0 0 | 0 0 0 0 0 1 | 0 0 1 0 1 0 | 0 1 0 0 1 1 | 0 1 1 1 0 0 | 1 0 0 1 0 1 | 1 0 1 1 1 0 | 1 1 1 1 1 1 | 1 1 0
The matrix is Eqn 5.62 on page 155.:
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
Let x=1, z=0. Then:
x'= 1 y'= y z'= y
and we've cloned y in the classical case, where the inputs are each 0 or 1.
This matrix is nonsingular and so is also legal in a quantum circuit.
(Looking ahead a little), try $y= \frac{1}{\sqrt{2}} | 0> + \frac{1}{\sqrt{2}} | 1>$, which is an equal superposition of 0 and 1. Using x=1, z=0, the input will be
$\frac{ | 1, 0, 0> + | 1, 1, 0>}{\sqrt{2}}$
and the state is
$(0, 0, 0, 0, \frac{1}{\sqrt{2}} , 0, \frac{1}{\sqrt{2}} , 0)^T$
That's an equal superposition of 2 of the possible 8 classical input states.
Multiplying that by the matrix gives
$\frac{ | 1, 0, 0> + | 1, 1, 1>}{\sqrt{2}}$
Instead of cloning y into z, this entangled y and z.
An operation that is simple on classical input can be more complicated on quantum inputs.
This isn't new; we already know how to entangle two qbits.
Engangling isn't the same as cloning. The point of cloning is that we could operate on the two bits separately. If they're engangled, operating on one affects the other.
You cannot measure the phase of qbit.
You can measure the relative phase of 2 qbits.
Many algorithms encode the answer as a phase shift of a qbit.
Phase kickback means that a gate that runs one way, e.g., the control bit affects an output bit, can be made to run the other way, e.g., the control bit is changed, by making the other bit a Hadamad basis.
Coined by Preskill in 2012.
Google claimed this in Oct 2019 on a specific (artificial?) problem; see Google section.
IBM disagrees.
IBM started this.
Alibaba followed.
Then D-Wave Leap, Rigetti, Amazon AWS Braket and Quantum solutions lab, Microsoft Azure.
IBM's intent is to entangle their computers in different sites; exponentially increasing power.
Proponents say that it's better than transmon qbits.
"To date, we’ve run single-qubit gates on a 79 ion chain, and complex algorithms on chains of up to 11 ions."
This is not comparable to quantum gates and circuits like IBM has.
It minimizes a function by testing many solutions in parallel.
See details in the D-Wave section.
Qbit count is not comparable to gate models.
Operates at room temperature.
See Xanadu below.
These companies have their own hardware.
They have several quantum computers, up to 53 qbits.
The older ones are freely available on the web; see https://quantum-computing.ibm.com/
Note that you can put gates between only adjacent qbits.
You submit a batch job and get emailed when it runs.
IBM github site: https://github.com/Qiskit with
a free simulator.
It doesn't match all the physical complexity of the real computer, but it's a good start.
and tutorials and presentations.
and a SW development framework. https://qiskit.org/
You can create a quantum computation program either by
designing a circuit, or
using a programming language.
IBM Introduces First Integrated Quantum Computing System for Commercial Use
Go Behind-the-Scenes of a Quantum Experiment (2:10) https://quantumexperience.ng.bluemix.net/qx/community/question?questionId=5ae975690f020500399ed39a&channel=videos
or
https://www.youtube.com/watch?v=tfZpJLdkzRU&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=7
A Qubit in the Making (2:01)
https://www.youtube.com/watch?v=2pB87H3_F_c&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=10&t=0s
Behold the Mighty Qubit (2:51) https://www.youtube.com/watch?v=_P7K8jUbLU0&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=10
Classical and Quantum Randomness (3:39) https://www.youtube.com/watch?v=8kyJfAC4VAo&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=6
Quantum Entanglement (2:21) https://www.youtube.com/watch?v=RmXasxLm43k&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=5
Benchmarking Quantum Systems (1:58) https://www.youtube.com/watch?v=-7L5o-mzLqU&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=8
Quantum Pong — Programming on Quantum Computers Season 1 Ep 1 3:54 by Abraham Asfaw.
IBM publishes its quantum roadmap, says it will have a 1,000-qubit machine in 2023
https://quantumcomputing.stackexchange.com/questions/tagged/ibm-q-experience
https://quantumcomputing.stackexchange.com/questions/tagged/qiskit
Quantum Algorithms for Applications from qiskit
This is in Huawei HiQ, an open-source software framework for quantum computing.
https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations
When you design a circuit here, you don't need to simulate it elsewhere. It shows you the probabilities.
Dual view: you can see and edit both the circuit and the QASM code.
There are some sample programs in https://github.com/Qiskit/openqasm.git
Example circuits in https://quantum-computing.ibm.com/docs/iqx/example-circuits .
Tangle Lake has 49 superconducting qbits.
Produced in Oregon.
Partners with QuTech in Netherlands.
https://www.intel.com/content/www/us/en/research/quantum-computing.html
Sycamore has 54 (-> 53) transmon qbits in 9x6 array, each coupled to 4 neighbors.
Google quantum General web site.
Day 1 opening keynote by Hartmut Neven (Quantum Summer Symposium 2020) 29:58.
QuantumCasts link to some videos, including the following.
Introduction to Quantum Chess (Quantum Summer Symposium 2020) 13:53.
Quantum Money (Quantum Summer Symposium 2020) 15:56. Peter Shor. It's fun to see what Shor is thinking about now.
QSI Seminar: Dr Marissa Giustina, Google Research, Building Google's Quantum Computer, 09/06/2020 55:52.
Programming a quantum computer with Cirq (QuantumCasts) 10:39.
They make a different type of quantum computer, called a quantum annealer. They have been in the news lately, e.g.,
https://arstechnica.com/science/2020/09/d-wave-releases-its-next-generation-quantum-annealing-chip/
Quantum Programming 101: Solving a Problem From End to End | D-Wave Webinar 54:25.
"Want to learn how to program a quantum computer? In this webinar, we explain how to do so by running through a complete, simple example. We explain how to formulate the problem, how to write it, and how to tune it for best results. "
"This webinar is intended for those with little or no experience programming on a D-Wave quantum computer. After watching, get free time on Leap, the quantum cloud service at https://cloud.dwavesys.com/leap/signup/ "
Slides from Programming Quantum Computers: A Primer with IBM Q and D-Wave Exercises by Frank Mueller, Patrick Dreher, Greg Byrd held at PPoPP (Feb 2019) ASPLOS'19 (Apr 2019),
Part 3: D-Wave -- Adiabatic Quantum Programming
D-Wave factoring tutorial and other demos
including Jupyter notebooks (you have to login for them).
founders from Maryland/College Park and Duke.
trapped ion
32 qbits.
low error rate
excellent quantum volume
will be available from Microsoft Azure and Amazon AWS Braket.
https://ionq.com/posts/october-01-2020-most-powerful-quantum-computer
H1: trapped ion.
10 qbits,
full connectivity,
can read isolated qbits in mid-computation,
hi-res rotations.
JP Morgan experimenting with it.
Zdnet: Honeywell's System Model H1 quantum computer available to enterprises
They partner with Microsoft,, Experience quantum impact with Azure Quantum, Cambridge Quantum Computing, Zapata Computing, etc.
Berkeley-based
founder is ex-IBM
has lots of tools
available via AWS etc
technical details are sparse
has been absorbing venture capital
"Recently, investors are gambling more on the middleware layer of a quantum computing stack. These are companies like Zapata, Q-CTRL, Quantum Machines and Aliro, which improve the performance of quantum computers and create an easier user experience"
makes optimistic promises (8/8/18):
https://medium.com/rigetti/the-rigetti-128-qubit-chip-and-what-it-means-for-quantum-df757d1b71ea
https://venturebeat.com/2020/09/02/xanadu-photonics-quantum-cloud-platform/
Uses photonics.
Operates primarily at room temperature.
Up to 24 qbits, gate depth of 12.
Has free SW tools, some of which can compile to other quantum technologies.
Expected good applications: graphs and networks, machine learning, and quantum chemistry.
They expect to scale up better than competing technologies.
Alibaba
1QBit
CQC
QC Ware
QSimulate
Quantum Circuits
Rahko
Zapata
These companies resell others' computers as a cloud service.
https://aws.amazon.com/braket/
"Amazon Braket is a fully managed quantum computing service that helps researchers and developers get started with the technology to accelerate research and discovery. Amazon Braket provides a development environment for you to explore and build quantum algorithms, test them on quantum circuit simulators, and run them on different quantum hardware technologies."
"...quantum annealers from D-Wave, and gate-based computers from Rigetti and IonQ."
They offer a cloud service on 3 platforms: Honeywell, IonQ, QCI.
A lot of stuff, with a low S/N.
Azure Quantum Developer Workshop. 5:05:25.
A little diffuse.
For faster quantum computing, Microsoft builds a better qubit 11/7/2019.
Microsoft Quantum Documentation gateway to a lot of stuff.
Microsoft, e.g. Quantum Computing for Computer Scientists 1:28:22.
This is the same viewpoint as the textbook, but the speaker is different.
This talk discards hand-wavy pop-science metaphors and answers a simple question: from a computer science perspective, how can a quantum computer outperform a classical computer? Attendees will learn the following:
Representing computation with basic linear algebra (matrices and vectors)
The computational workings of qbits, superposition, and quantum logic gates
Solving the Deutsch oracle problem: the simplest problem where a quantum computer outperforms classical methods
Bonus topics: quantum entanglement and teleportation
The talk concludes with a live demonstration of quantum entanglement on a real-world quantum computer, and a demo of the Deutsch oracle problem implemented in Q# with the Microsoft Quantum Development Kit. This talk assumes no prerequisite knowledge, although comfort with basic linear algebra (matrices, vectors, matrix multiplication) will ease understanding.
See more at https://www.microsoft.com/en-us/research/video/quantum-computing-computer-scientists/
Good ref is Chapter 6, Algorithms of Quantum Computing for Computer Scientists, published in 2000. Algorithms don't change fast. It does omit new things like HHL.
For these examples, the quantum algorithm is quite different from the classical algorithm, and is asymptotically faster.
Current research is deciding what algorithms can be made faster.
p 172: Any function can be made invertible by adding a control bit.
Major categories:
Cryptography
Quantum search
Quantum simulation
Quantum annealing and adiabatic optimization
Nice summary: https://en.wikipedia.org/wiki/Quantum_computing
Algorithm summary:
Some, but not all, are faster.
Bounded-error quantum polynomial time (BQP)
"is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances" - https://en.wikipedia.org/wiki/BQP
Includes integer factorization and discrete log.
Relation to NP is unknown (big unsolved problem).
Searching problems:
Find the answer to a puzzle.
Math examples: factor an integer, solve a polynonial equation.
Testing validity of a putative solution is easy.
Finding that putative solution, naively, requires testing all possibilities.
Quantum computation can solve some searching problems faster.
This is probabilistic or noisy; often the found solution is wrong.
So you repeat the computation enough times that the error rate is acceptably low.
Some classical algorithms are similar. There is an excellent probabilistic primality algorithm.
The quantum algorithms are quite complex. (i.e., I'm still learning them.)
Algorithms, another view
Hadamard matrix rotates the pure state to an entangled superposition.
Then we operate in parallel on each state in the superposition.
Finally we separate out the desired answer.
Grover's algorithm:
Given a black box with N inputs and 1 output.
Exactly one input makes the output 1.
Problem: which one?
Classical solution: Try each input, T=N.
Quantum: $T=\sqrt(N)$.
Probabilistic.
Apps: mean, median, reverse a crypto hash, find collisions, generate false blocks.
Can extend to quantum partial search.
Grover's algorithm is optimal.
This suggests that NP is not in BQP .
Shor's algorithm:
Factorize an integer.
in BQP.
almost exponentially faster than best classical algorithm.
Largest examples I can find:
We have a black box F(x) -> x'.
We're told that F is either balanced or constant.
How to determine which?
We can input any x and see the result.
Classically: eval F(0) and F(1).
That took two evals and some comparisons.
All that matters is the number of evals. We assume that they're slower than everything else.
Quantumly (quantumicly?) we can determine which type F is with only one eval plus some extra matrices.
Now $F: \{0,1\}^n \to \{0,1\}$.
We're told that it's either constant or balanced. It's not neither.
Which is it?
Classically, we need n/2+1 evals of F.
Quantumly, we need only 1.
Blackbox $F: \{0,1\}^n \to \{0,1\}^n$
For some unknown $c$, $F(x\oplus c) = F(x)$.
Determine $c$.
Blackbox $F: \{0,1\}^n \to \{0,1\}$
For only one x, F(x) = 1. Otherwise F(x)=0.
Determine x.
Classically: T(n)=O(n).
Quantumly: $T(n) = O(\sqrt{n})$.
Introduction to Quantum Computing (18) - Grover's Algorithm: Quantum Problem Statement (4:24)
Introduction to Quantum Computing (19) - Grover's Algorithm: Outline (16:09)
Introduction to Quantum Computing (20) - Grover's Algorithm: Subspace (7:42)
Introduction to Quantum Computing (21) - Grover's Algorithm: Geometric Interpretation
Introduction to Quantum Computing (23) - Grover's Algorithm: Implementation (9:33)
Introduction to Quantum Computing (24) - Grover's Algorithm: IBM Quantum Experience (11:39)
This algorithm is deterministic.
https://www.quantiki.org/wiki/deutsch-jozsa-algorithm
Quick summary; doesn't say why it works.
https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html
This is an intro to Qiskit. The terminology is confusing. E.g., Register 1 has q0 q1 q2. Register 2 has q3. The run buttons don't seem to work.
https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm
This is a nice detailed description.
Quantum Machine Learning - 37 - Overview of the HHL Algorithm 5:48.
quick, deep, intro.
Quantum algorithm for solving linear equations 36:31.
quite understandable.
Quantum Algorithms for Systems of Linear Equations (Quantum Summer Symposium 2020) 19:22.
IBM Quantum Algorithms for Applications from qiskit
E.g., Fourier transform and HHL.
This is in Huawei HiQ, an open-source software framework for quantum computing.
https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations
A difficulty is to compile to the limited connectivity of the machine
ProjectQ open-source software framework for quantum computing.
Programming Quantum Computers: A Primer with IBM Q and D-Wave Exercises . Tutorial given at a few conferences.
https://www.hpcwire.com/off-the-wire/quantum-computing-inc-releases-version-1-1-of-mukai-middleware/
https://tbri.com/webinars/middleware-the-quantum-computing-differentiator/ "An integral piece of quantum computing’s success is the middleware bridging existing code and algorithms to the new logical circuitry being established that sits on top of the quantum circuits. This integration and abstraction will allow the technology to process complex algorithms to provide the outcomes the hardware enables."
excellent videos from this Delft research group.
Per Delsing: Superconducting qubits as artificial atoms 28:59.
He's describing a different computer from IBM's.
The Taming of the Superconducting Qubit: A Tale of Loss 35:47.
Presenter: Conal Murray, Research Staff Member, IBM Research
The potential of quantum computing to enable new ways of solving problems considered intractable on classical computing platforms relies on our understanding of how qubits operate. Qubit scaling follows different metrics than those associated with classical computing, driven by the requirement that the fragile states they possess can be retained for sufficiently long times. After a brief introduction into superconducting transmon qubits, I will discuss how dielectric loss impacts their relaxation times and how we can effectively model such behavior using analytical and computational approaches. The resulting analysis provides guidance into the design aspects associated with such qubits. A secondary issue that follows from manufacturing greater numbers of qubits involves unwanted communication among them. In particular, resonance modes generated in the substrate on which they reside can limit their operating frequencies. It is known that incorporating grounded, through-silicon vias can increase the corresponding cutoff frequency within the substrate. I will show how we can predict the resulting spectrum by considering the array of vias as an effective photonic crystal to arrive at a fundamental frequency dependent on the particulars of the via geometry.
Quantum Computing UK nice set of docs and examples.
Ricardo Diaz recommends this book: Something Deeply Hidden: Quantum Worlds and the Emergence of Spacetime .
There are now several business reports on the industry.
Quantum computing hasn't solidly proved itself yet. However it's now in the engineering phase - realizing what we basically know how to do.
IMO the physicists have done it again (last time was atomic energy). This will be a fundamental transformation of computing.
Certain searching algorithms will be exponentially faster.
Algorithm design still needs research. Algorithms are quite complex.
Major application areas like drug design.
Several viable technologies competing.
Several HW companies.
Competing toolsets being developed.
Various service platforms to provide simulators and the HW.
Recommendation (remember I'm SW):
Be agnostic wrt platform (we don't know who will win).
Have people use AWS etc to learn and develop apps. No capital investment needed.
Work developing and/or using middleware, which is newer area.
RPI-specific:
Merely playing catchup is a losing game. Need something new.
Assume that IBM etc will make the computers. The big problem with new HW is always how to use it. The ability of customers to use a new tool can determine whether it succeeds.
Include other RPI programs?
Gamify this using Game and Sim?
Work with tetherless world?
I'm still thinking.
Table of contents
Optional enrichment material.
It costs to register for this, except the equipment show.
It's this week and next week.
One use for this is to find interesting presentations, and then search for free versions.
Google quantum General web site.
Day 1 opening keynote by Hartmut Neven (Quantum Summer Symposium 2020) 29:58.
We'll watch some or all, depending on how interesting it it.
QuantumCasts link to some videos, including the following.
Introduction to Quantum Chess (Quantum Summer Symposium 2020) 13:53.
Quantum Money (Quantum Summer Symposium 2020) 15:56. Peter Shor. We'll watch the start. It's fun to see what Shor is thinking about now.
Due 2020-11-16 4:45pm in gradescope.
Teams of up to 3 are ok.
This project is to introduce yourself to quantum computing on Amazon Braket . It's sufficient to use the simulator. Wander around the web site. Set up an account. Create a simple program. Simulate it. Write a report on your observations.
This will probably cost you a few dollars, but not too much. If you feel that I'm being unfair to ask this, contact me. I'll give you a replacement homework.
Total: 20 points.
Table of contents
I'm virtually attending ACM SIGSPATIAL 2020 this week, and asked the Google speaker at the sponsor presentation session. He said that students should know how to design SW for longterm maintainability.
Know the balance balance between perfection and speed and effectiveness.
He also mentioned as a blue sky skill that students know something about quantum computing.
The Oracle rep said, API design, ability to develop modular and maintainable SW that catches and logs errors with sufficient diagnostics.
Everyone mentioned being able to apply ML to different domains. But then, one definition of ML is, "hard and unsolved important problem".
I just noticed that they were no longer permitted readable; dunno when that had happened. Fixed it. However no one ever complained. :-(
Today we are lucky to have Prof Jian Shi, Materials Science and Engineering, to talk about some physics aspects of quantum computing.
Google quantum General web site.
Day 1 opening keynote by Hartmut Neven (Quantum Summer Symposium 2020) 29:58.
We'll watch some or all, depending on how interesting it it.
QuantumCasts link to some videos, including the following.
Introduction to Quantum Chess (Quantum Summer Symposium 2020) 13:53.
Quantum Money (Quantum Summer Symposium 2020) 15:56. Peter Shor. We'll watch the start. It's fun to see what Shor is thinking about now.
Table of contents
I'm trying to keep things relaxed. I introduce you to fun stuff that you can pursue on your own.
Is this pace reasonable?
Do you want deeper math?
Do you want required readings/viewings before class?
(Everyone's camera is off but for mine.) Do you want me to require you to enable your cameras, and then I call on you with questions?
The WIRED Guide to Quantum Computing Nice non-too-technical summary of the history. The theory preceded the realization. This happens sometimes, e.g., with atomic energy.
Quantum Pong — Programming on Quantum Computers Season 1 Ep 1 3:54 by Abraham Asfaw.
Quantum Machine Learning - 37 - Overview of the HHL Algorithm 5:48.
quick, deep, intro.
Quantum algorithm for solving linear equations 36:31.
quite understandable. We'll watch some.
Quantum Algorithms for Systems of Linear Equations (Quantum Summer Symposium 2020) 19:22.
watch this if you wish.
IBM Quantum Algorithms for Applications from qiskit
Run through the fourier transform and HHL on your own.
This is in Huawei HiQ, an open-source software framework for quantum computing.
https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations
They offer a cloud service on 3 platforms: Honeywell, IonQ, QCI.
A lot of stuff, with a low S/N.
Azure Quantum Developer Workshop. 5:05:25.
This is a little diffuse; watch on your own if you wish.
For faster quantum computing, Microsoft builds a better qubit 11/7/2019.
Microsoft Quantum Documentation gateway to a lot of stuff.
Due 2020-11-09 4:45pm in gradescope.
Teams of up to 3 are ok.
Pick a quantum software project not discussed in class, and write a page on it. Summarize it, perhaps give some example code. How widely used is it? Is the project live?
A possible source is https://quantumcomputingreport.com/tools/ .
Write a page with concise technical summary of Microsoft's role in quantum computing. I.e., summarize the mass of stuff I linked to.
Total: 20 points.
Table of contents
I'll add some help and give you more time.
Some other profs at RPI who work with quantum computing have generously agreed to talk to the class. So, far the schedule is:
Jian Shi. Nov 5.
Sufei Shi. Nov 30.
Edwin Fohtung. TBD.
You cannot measure the phase of qbit.
You can measure the relative phase of 2 qbits.
Many algorithms encode the answer as a phase shift of a qbit.
Phase kickback means that a gate that runs one way, e.g., the control bit affects an output bit, can be made to run the other way, e.g., the control bit is changed, by making the other bit a Hadamad basis.
We'll see an example on the IBM Q.
Zdnet: Honeywell's System Model H1 quantum computer available to enterprises
They partner with Microsoft,, Experience quantum impact with Azure Quantum, Cambridge Quantum Computing, Zapata Computing, etc.
Quantum Algorithms for Applications from qiskit
This is rather deep; we may skim it.
This is in Huawei HiQ, an open-source software framework for quantum computing.
https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations
Table of contents
Quantum Programming 101: Solving a Problem From End to End | D-Wave Webinar 54:25.
"Want to learn how to program a quantum computer? In this webinar, we explain how to do so by running through a complete, simple example. We explain how to formulate the problem, how to write it, and how to tune it for best results. "
"This webinar is intended for those with little or no experience programming on a D-Wave quantum computer. After watching, get free time on Leap, the quantum cloud service at https://cloud.dwavesys.com/leap/signup/ "
We'll watch part in class; finish it on your own.
Slides from Programming Quantum Computers: A Primer with IBM Q and D-Wave Exercises by Frank Mueller, Patrick Dreher, Greg Byrd held at PPoPP (Feb 2019) ASPLOS'19 (Apr 2019),
Part 3: D-Wave -- Adiabatic Quantum Programming
We'll click through to some of the things it links to, like the
D-Wave factoring tutorial and other demos
including Jupyter notebooks (you have to login for them).
Sir Roger Penrose & Dr. Stuart Hameroff: CONSCIOUSNESS AND THE PHYSICS OF THE BRAIN 1:52:47. Among other things, Penrose invented Penrose tilings and shared this years Physics Nobel.
Microsoft, e.g. Quantum Computing for Computer Scientists 1:28:22.
This is the same viewpoint as the textbook, but the speaker is different.
Watch this if you're still confused.
This talk discards hand-wavy pop-science metaphors and answers a simple question: from a computer science perspective, how can a quantum computer outperform a classical computer? Attendees will learn the following:
Representing computation with basic linear algebra (matrices and vectors)
The computational workings of qbits, superposition, and quantum logic gates
Solving the Deutsch oracle problem: the simplest problem where a quantum computer outperforms classical methods
Bonus topics: quantum entanglement and teleportation
The talk concludes with a live demonstration of quantum entanglement on a real-world quantum computer, and a demo of the Deutsch oracle problem implemented in Q# with the Microsoft Quantum Development Kit. This talk assumes no prerequisite knowledge, although comfort with basic linear algebra (matrices, vectors, matrix multiplication) will ease understanding.
See more at https://www.microsoft.com/en-us/research/video/quantum-computing-computer-scientists/
Quantum Algorithms for Applications from qiskit
This is rather deep; we may skim it.
Table of contents
The transmon qubit | QuTech Academy 6:03.
The Hamiltonian of a system is an equation for its total energy (kinetic and potential) in terms of parameters like position and momentum.
Alexandre Blais - Quantum Computing with Superconducting Qubits (Part 1) - CSSQI 2012 45:11.
We'll watch part. You're encouraged to finish it on your own.
Control of transmon qubits using a cryogenic CMOS integrated circuit (QuantumCasts) 35:47.
Control of transmon qubits using a cryogenic CMOS integrated circuit talk is presented by Research Scientist Joe Bardin for the APS March Meeting 2020.
Superconducting quantum processors are controlled and measured in the analog domain and the design of the associated classical-to-quantum interface is critical in optimizing the overall performance of the quantum computer. Control of the processor is achieved using a combination of carefully shaped microwave pulses and high-precision time varying flux biases. Measurement of quantum states is typically achieved using dispersive readout, which requires a low-power pulsed microwave drive and a near quantum-limited readout chain. For control of a single qubit, a typical system employs two high-speed high-resolution (e.g., 1 Gsps/14 bit) digital-to-analog converters (DACs) and a single-sideband modulator to generate microwave control pulses. A third DAC with similar specifications is used for flux-bias control. A typical readout channel may service on the order of five qubits and contains yet another pair of DACs, with a single-sideband modulator employed to generate a stimulus signal. For measurement, the readout chain also employs a series of cryogenic amplifiers followed by further amplification, IQ demodulation, and high-speed digitization at room temperature. For today’s prototype systems with on the order of 50-100 qubits, keeping most of the electronics at room temperature makes sense. However, achieving fault tolerance—a long term goal of the community—will require implementing systems with on the order of 10^6 qubits and today’s brute force control and readout approach will not scale to these levels. Instead, a more integrated approach will be required. In this talk, we will present a review of recent work towards implementing a scalable cryogenic quantum control and readout system using silicon integrated circuit technology. After motivating the work, we will describe the design and characterization of a prototype cryogenic XY controller for transmon qubits. Detailed measurement results will be presented. The talk will conclude with a discussion of future work.
You may watch this on your own.
Per Delsing: Superconducting qubits as artificial atoms 28:59.
I might start showing this around 6:00 and show to around 16:00. He's describing a different computer from IBM's.
The Taming of the Superconducting Qubit: A Tale of Loss 35:47.
Presenter: Conal Murray, Research Staff Member, IBM Research
The potential of quantum computing to enable new ways of solving problems considered intractable on classical computing platforms relies on our understanding of how qubits operate. Qubit scaling follows different metrics than those associated with classical computing, driven by the requirement that the fragile states they possess can be retained for sufficiently long times. After a brief introduction into superconducting transmon qubits, I will discuss how dielectric loss impacts their relaxation times and how we can effectively model such behavior using analytical and computational approaches. The resulting analysis provides guidance into the design aspects associated with such qubits. A secondary issue that follows from manufacturing greater numbers of qubits involves unwanted communication among them. In particular, resonance modes generated in the substrate on which they reside can limit their operating frequencies. It is known that incorporating grounded, through-silicon vias can increase the corresponding cutoff frequency within the substrate. I will show how we can predict the resulting spectrum by considering the array of vias as an effective photonic crystal to arrive at a fundamental frequency dependent on the particulars of the via geometry.
http://meetings.aps.org/Meeting/MAR20/Session/P28.2
We may watch the first part. This talk is more technical.
We've seen some of the excellent videos from this Delft research group.
Due 2020-10-29 4:45pm in gradescope.
Teams of up to 3 are ok.
This homework is to program the IBM Q yourself.
It is from Programming Quantum Computers: A Primer with IBM Q and D-Wave Exercises by Frank Mueller, Patrick Dreher, Greg Byrd held at PPoPP (Feb 2019) ASPLOS'19 (Apr 2019).
Read and do parts 1 and 2. Run deutsch-josza.ipynb.
Upload a printout of the result. Include enough to make a convincing case that you got it to run.
Total: 20 points.
Table of contents
Feynman was the first to propose the theoretical idea of a quantum computer.
Richard Feynman - Quantum Mechanics 4:01.
Extracted from HD Feynman: FUN TO IMAGINE complete 1080p 1:06:49. Recorded in 1983.
(to help you with the homework)
Can we make quantum technology work? | Leo Kouwenhoven | TEDxAmsterdam (18:19)
Sutor: Under the hood of IBM Q somewhat duplicative of his other video, but a little deeper.
Due 2020-10-23 4:45pm in gradescope.
Teams of up to 3 are ok.
Watch the 4 videos on Shor's algorithm that I first posted in class 7 and reposted today in class 13.
Write 400-500 words summarizing it. Be technical. Include some figures and equations.
Make your writeup look professional, as if you were submitting it to a conference.
Total: 20 points.
Table of contents
R Dia and N Pag and C Woo. EPR paradox.
C Bar and L Rob and M Vis. E.5.1: Maxwell’s Demon, Landauer’s Principle, and the Physics of Information.
Y Zha.
https://quantum-computing.ibm.com/docs/iqx/guide/introducing-qubit-phase
Can represent qbit with probability of being in 1 and a phase.
Phase is not directly measurable.
Gates can change phase, i.e., rotate the qbit.
Gates: T, S, Z, U1, etc.
Table of contents
A Mar. Quantum erasers.
J DeG. Fourier Transforms.
I Phi. E.7.3 - Functional Quantum Programing: QML.
J Cun. Finite Automata E.8.2.
Quantum Computing UK nice set of docs and examples.
ProjectQ open-source software framework for quantum computing.
Programming Quantum Computers: A Primer with IBM Q and D-Wave Exercises . Tutorial given at a few conferences.
Ricardo Diaz recommends this book: Something Deeply Hidden: Quantum Worlds and the Emergence of Spacetime .
Quantum-Computing-for-Computer-Scientists.
Wikipedia.
I might play only the start of these videos, to tease you into watching the rest on your own.
Quantum applications, e.g., from qiskit docs.
Other quantum computers, e.g., D-Wave.
Table of contents
C Glo.
JH Hon and N Mur. E.11.3 Current Quantum Crypto Implementations
D Pal. RSA
J Rol. E.11.1 - Decoherence and the Emergence of the Classical World
C McG and S Sur. Bell Theorem.
DC Dav. E.11.2 (A Comparison of Extant Approaches to Quantum Hardware)
Table of contents
are listed in piazza. (I put temporary things there.)
https://en.wikipedia.org/wiki/D-Wave_Systems
They make a different type of quantum computer, called a quantum annealer. It is not comparable to quantum gates and circuits like IBM has. D-Wave minimizes a function by testing many solutions in parallel. They have been in the news lately, e.g.,
https://arstechnica.com/science/2020/09/d-wave-releases-its-next-generation-quantum-annealing-chip/
One way that I learn a new topic is to read several different intros.
https://towardsdatascience.com/introduction-to-quantum-programming-a19aa0b923a9?gi=69d861e26d80
https://medium.com/@jonathan_hui/qc-programming-with-quantum-gates-8996b667d256
https://medium.com/@jonathan_hui/qc-programming-with-quantum-gates-2-qubit-operator-871528d136db
https://www.cl.cam.ac.uk/teaching/0910/QuantComp/notes.pdf
They have a nice description of measurement starting at slide 10.
Each measurement operator has a basis vector set.
The operator represents the qbit as a linear combo of the basis vectors.
Then it projects the qbit onto one of the basis vectors, with probability being the length of that component.
It is possible for two different qbits to measure the same in some basis, but measure different in a different basis.
When you design a circuit here, you don't need to simulate it elsewhere. It shows you the probabilities.
Dual view: you can see and edit both the circuit and the QASM code.
There are some sample programs in https://github.com/Qiskit/openqasm.git
We'll see how to clone that repository.
We'll use and mod their Deutsch algorithm.
We'll try the example circuits in https://quantum-computing.ibm.com/docs/iqx/example-circuits .
We'll also see a reversible circuit for (7x mod 15).
That sort of circuit is used in Shor's integer factorization algorithm.
Shor's algorithm
How IBM Q works (the hardware).
Table of contents
Here. Deadline: Monday, November 2, 2020.
The quantum states of some system are solutions of a linear PDE. There is a basis set of solutions. Linear combos are also solutions. That's superposition.
IBM’s Roadmap For Scaling Quantum Technology
We'll see the HW later.
I'd like you to try the qiskit tutorial yourself, now, in class.
Do you have python?
The following is a summary from https://qiskit.org/documentation/install.html
I'm trying to avoid using anaconda, to keep things a little simpler.
#. Create a free IBM Quantum Experience account.
pip install 'qiskit[visualization]'
#, run python.
in python:
import qiskit
Follow the tutorial.
Ask questions.
Table of contents
We're not finished with Quantum Computing for Computer Scientists and algorithms. However today we'll start seeing IBM's role in quantum computing.
These are available on IBM's site (you need to create an account) and on youtube.
Go Behind-the-Scenes of a Quantum Experiment (2:10) https://quantumexperience.ng.bluemix.net/qx/community/question?questionId=5ae975690f020500399ed39a&channel=videos
or
https://www.youtube.com/watch?v=tfZpJLdkzRU&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=7
A Qubit in the Making (2:01)
https://www.youtube.com/watch?v=2pB87H3_F_c&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=10&t=0s
Behold the Mighty Qubit (2:51) https://www.youtube.com/watch?v=_P7K8jUbLU0&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=10
Classical and Quantum Randomness (3:39) https://www.youtube.com/watch?v=8kyJfAC4VAo&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=6
Quantum Entanglement (2:21) https://www.youtube.com/watch?v=RmXasxLm43k&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=5
Benchmarking Quantum Systems (1:58) https://www.youtube.com/watch?v=-7L5o-mzLqU&list=PLOFEBzvs-VvpzQnlazij7cL1mjKvJTAwk&index=8
Experiment with Basic Quantum Algorithms (Ali Javadi-Abhari, ISCA 2018) (19:05) https://www.youtube.com/watch?v=M1UHi9UXTWI&list=PLOFEBzvs-VvruANdBhTb-9YRDes07pZWQ&index=2
They have several quantum computers.
The older ones are freely available on the web.
Those have 5 and 15 qbits; see https://quantum-computing.ibm.com/
Note that you can put gates between only adjacent qbits.
You submit a batch job and get emailed when it runs.
IBM github site: https://github.com/Qiskit with
a free simulator.
It doesn't match all the physical complexity of the real computer, but it's a good start.
and tutorials and presentations.
and a SW development framework. https://qiskit.org/
You can create a quantum computation program either by
designing a circuit, or
using a programming language.
Install it on your machine.
Create and run the demo program.
Try the Getting Started tutorial.
Since I'm still learning, I have to say circ.draw() not circ.draw('mpl')
https://www.ibm.com/quantum-computing/
Browse around the website.
Look at the topologies of some machines.
Create an account for yourself.
Play with the graphical composer.
Submit a job.
Look at the output.
Table of contents
Homework 3 is student in-class presentations in 2 weeks.
Feel free to use piazza to solicit partners. Teaming is optional here, in contrast to some online classes that assign teams.
Colleges encourage or require teamwork because teams get more done. Working with other people is a valuable skill. Someday I hope to learn it :-)
You don't need to watch all of them, but sample them.
Which problems can quantum computers solve exponentially faster than classical computers? David Gosset, IBM quantum computing research scientist, explains why algorithms are key to finding out.
Can we make quantum technology work? | Leo Kouwenhoven | TEDxAmsterdam (18:19)
Experiment with Basic Quantum Algorithms (Ali Javadi-Abhari, ISCA 2018) (19:05)
Introduction to Quantum Computing (18) - Grover's Algorithm: Quantum Problem Statement (4:24)
Introduction to Quantum Computing (19) - Grover's Algorithm: Outline (16:09)
Introduction to Quantum Computing (20) - Grover's Algorithm: Subspace (7:42)
Introduction to Quantum Computing (21) - Grover's Algorithm: Geometric Interpretation
Introduction to Quantum Computing (23) - Grover's Algorithm: Implementation (9:33)
Introduction to Quantum Computing (24) - Grover's Algorithm: IBM Quantum Experience (11:39)
Quantum algorithms are different and difficult, so reading multiple presentations may help. Here are some; some are on IBM's Qiskit site.
https://www.quantiki.org/wiki/basic-concepts-quantum-computation - Read at least the start.
Quantiki's biggest problem is that many links are dead.
This algorithm is deterministic.
https://www.quantiki.org/wiki/deutsch-jozsa-algorithm
Quick summary; doesn't say why it works.
https://qiskit.org/textbook/ch-algorithms/deutsch-jozsa.html
This is an intro to Qiskit. The terminology is confusing. E.g., Register 1 has q0 q1 q2. Register 2 has q3. The run buttons don't seem to work.
https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm
This is a nice detailed description.
This algorithm is probabilistic.
This will be student presentations of some idea in quantum computing.
They will be in two weeks, on Oct 5 and 8.
You may do them in teams of up to 3.
A 1-person presentation will be 6-7 minutes. Two or more people will be 10-12 minutes.
So that the class ends on time, your time will start when it's your turn and will end the appropriate number of minutes later. You may also submit a video.
Pick a topic from Quantum Computing for Computer Scientists, in Appendix E, starting with E.3.
I'll set up forms for people to pick a date and a topic, so that no more than 10 people are on Oct 8, and people pick different topics.
Table of contents
A student recommended these two books to the class.
Quantum Computing: An Applied Approach by Jack Hidary
Quantum Computation and Quantum Information by Nielsen and Chuang
The first book is more relevant to the class because it has more hands on examples. The second book is good for more theoretical information on the topic, but is still really interesting.
I made some supplementary material on cloning (copying), which works in the classical world but not in the quantum world.
Classically, you can easily clone a bit. Consider a 2-bit system, $x, y$. Represent the state with a 4-vector
$s=\begin{vmatrix} a_0\\a_1\\a_2\\a_3\end{vmatrix}$
where exactly one $a_i=1$ and the other three are 0. E.g., if $a_3=1$ then $x=y=1$.
Here's a 2-input, 2-output circuit that clones the first bit.
$x'=x\\y'=x$
Its truth table is
x y | x'y' 0 0 | 0 0 0 1 | 0 0 1 0 | 1 1 1 1 | 1 1
The matrix M is:
1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1
That is, the final state is $s' = \sum_j M_{ij} b_j$
However, M is singular. So this is not a legal quantum circuit. Let's try again.
The better way is the 3-input Toffoli gate in Figure 5.66 on page 156. The function is
$x'=x \\ y'=y \\ z'= z \oplus xy$
The truth table is
x y z | x'y'z' 0 0 0 | 0 0 0 0 0 1 | 0 0 1 0 1 0 | 0 1 0 0 1 1 | 0 1 1 1 0 0 | 1 0 0 1 0 1 | 1 0 1 1 1 0 | 1 1 1 1 1 1 | 1 1 0
The matrix is Eqn 5.62 on page 155.:
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
Let x=1, z=0. Then:
x'= 1 y'= y z'= y
and we've cloned y in the classical case.
This matrix is nonsingular and so is legal in a quantum circuit.
Try $y= \frac{1}{\sqrt{2}} | 0> + \frac{1}{\sqrt{2}} | 1>$. Using x=1, z=0, the input will be
$\frac{ | 1, 0, 0> + | 1, 1, 0>}{\sqrt{2}}$
and the state is
$(0, 0, 0, 0, \frac{1}{\sqrt{2}} , 0, \frac{1}{\sqrt{2}} , 0)^T$
Multiplying that by the matrix gives
$\frac{ | 1, 0, 0> + | 1, 1, 1>}{\sqrt{2}}$
Instead of cloning y into z, this entangled y and z.
This isn't new; we already know how to engangle two qbits.
Engangling isn't the same as cloning. The point of cloning is that we could operate on the two bits separately. If they're engangled, operating on one affects the other.
Today's big new stuff.
As usual, I'm typing the important points into this blog, together with my observations and opinions.
The algorithms are all searching for an answer. (An alternative is algorithms that compute something, like inverting a matrix.)
For these examples, the quantum algorithm is quite different from the classical algorithm, and is asymptotically faster.
Current research is deciding what algorithms can be made faster.
p 172: Any function can be made invertible by adding a control bit.
We have a black box F(x) -> x'.
We're told that F is either balanced or constant.
How to determine which?
We can input any x and see the result.
Classically: eval F(0) and F(1).
That took two evals and some comparisons.
All that matters is the number of evals. We assume that they're slower than everything else.
Quantumly (quantumicly?) we can determine which type F is with only one eval plus some extra matrices.
Now $F: \{0,1\}^n \to \{0,1\}$.
We're told that it's either constant or balanced. It's not neither.
Which is it?
Classically, we need n/2+1 evals of F.
Quantumly, we need only 1.
Blackbox $F: \{0,1\}^n \to \{0,1\}^n$
For some unknown $c$, $F(x\oplus c) = F(x)$.
Determine $c$.
Blackbox $F: \{0,1\}^n \to \{0,1\}$
For only one x, F(x) = 1. Otherwise F(x)=0.
Determine x.
Classically: T(n)=O(n).
Quantumly: $T(n) = O(\sqrt{n})$.
Table of contents
We're doing chapters 4 and 5 of Quantum Computing for Computer Scientists.
I'm typing the important points into this blog.
This restates more solidly what they stated more informally earlier.
Consider a particle on a line, with possible positions $x_0, x_1, ... x_{n-1}$.
We don't do the continuous limit here.
$|x_i>$ means the particle is at position $x_i$.
We describe the state of the system by using a complex vector $[c_0, c_1, ... c_{n-1}]^T$.
$|x_0> \longmapsto [1, 0, ...]^T$. $\longmapsto$ means maps to.
$|x_1> \longmapsto [0, 1, 0, ...]^T$.
$|x_{n-1}> \longmapsto [0, 0, ..., 1]^T$.
Posit All vectors in $C^n$ are legal states for the particle.
$|\psi>$ is a general state
$|\psi> = c_0 | x_0> + c_1 | x_1 + ...$
$|\psi> \longmapsto [c_0, c_1, ...]^T$.
This is a linear combo of the $|x_i>$.
That's superposition.
Observing it causes transition to one state, with prob eqn 4.5.
$p(x_i) = \frac{ | c_i | ^2}{\sum_j | c_j | ^2 } $
$| \psi> \leadsto | x_i >$ .
$\leadsto$ means the first quantum state transitions to the second.
Spin is a property of most quantum particles.
You can measure its spin wrt the axis of your choice (subject to your equipment).
Wrt any given axis, the spin is up $|\uparrow>$ or down $\downarrow>$.
Particle is in a superposition of both spins.
$|\psi = c_0 | \uparrow> + c_1 | \downarrow>$.
Probability of observing in $|\uparrow>$
Measurement operator will cause state to transition to one of a set of specific states (depending on the operator).
$|\psi> \leadsto | \psi' >$.
Application of inner product.
Probability of transitioning from $\psi$ to $\psi'$ when measured = $<\psi' | \psi>$.
Each observable thing, e.g, position, has a Hermitian operator.
The possible observable values are its eigenvalues.
In the particle example, P = diag[$x_0, x_1, ...$].
If we do two observations, the second is affected by what we see in the first.
Skip pages 118-125.
Determine the value of an observable. If the observable is position, then a possible value might be 3.
Measuring causes the system to transition randomly to one eigenvector of the observable.
The probability is the transition amplitude.
(Not in book) One way to look at measuring is that the system is interacting with the outside world. Both are being affected, and the combo is reversible.
Evolution of a system is a unitary operator.
Reversible.
Schrodingers equation.
Tensoring the state spaces of the parts.
Entanglement again.
Example: create two paired spin particles from something with no spin. If you observe one particle to be $|\uparrow>$, then when you observe the other, it must be $|\downarrow>$. This is because spin is conserved.
Example 4.5.1, p 133
Exercise 4.5.3, p 135.
We've seen much of this earlier.
This puts classical gates and bits into quantum notation. This may help you understand quantum gates better.
Spelling: some say qbit others qubit.
Sample notation: AND $\!|01\!\!>\,\,=\,\,|0\!\!>$
There is a gate that will clone its input, i.e., make it fan out to two outputs.
Erasing info dissipates energy.
Block sphere. I don't personally find it that interesting. You may differ.
Can add one more input to make any gate into a controlled gate. E.g. ${}^c NOT$.
The classical cloning gate doesn't clone quantum states.
No-cloning.
Transporting or swapping is fine. (Star Trek got it right.)
Due 2020-09-21 4:45pm in gradescope.
Quantum Computing for Computer Scientists will be very useful.
Ok to work in groups of 3 and submit one solution.
(5 points) Exercise 3.2.6, p 85.
(2 points) Exercise 3.3.1, p 90.
(2 points) Exercise 3.4.3, p 101.
(2 points) Exercise 4.1.1, p 108.
(2 points) Exercise 4.1.3, p 109.
(5 points) Exercise 5.2.8, p 151.
Total: 18.
Table of contents
Did anyone have a problem with the resolution of the lecture 3 video being scaled down to 960x540 instead of the original 1920x1080? That cut the file size from 298MB to 145MB. It's annoying that Mediasite doesn't support H.265, so the codec has to be H.264. In future, I might increase the compression until people start objecting. The main effect of that would be motion artifacts; still images should be the same.
FYI, so far, a CLI is easier than an interactive tool.:
ffmpeg -i c03.mp4 -ss 1:00 -b:a 20k -vf "scale=iw/2:ih/2" c03s.mp4
This is being computed on my P73 laptop with a 6-core Xeon E-2276M CPU @ 2.80GHz (up to 4.70 GHz with Turbo Boost), 128GB of ECC memory, and Quadro RTX 5000 with 16GB. (The only problem with the laptop is it weighs 8 lb.)
(I wanted to mix up the math with less mathy stuff).
From end of section 2.3, p.52 to 2.6.
P 52. Transition matrix to convert a vector representation from the canonical basis this another basis is the Hadamark matrix.
Section 2.4. Add an inner product operator to the complex vector space. Note the conjugates in the rules; you don't see them with a real vector space.
Norm, aka length.
We won't need limits etc.
Section 2.5 Eigenvalues and eigenvectors
Eigenvalues don't depend on the representation. Converting to a new basis set doesn't change them.
Geometrically, in 2D, in you transform a circle centered at origin, eigenvalues are lengths of the axes. Eigenvectors are the axes.
Section 2.6 Hermitian and unitary matrices
P 39. Adjoint: conjugate transpose of matrix.
If you use its eigenvectors as a basis, then the matrix diagonalizes to a list of its eigenvalues.
P 62. Hermitian matrix: it is its adjoint.
Unitary: its inverse is its adjoint.
Geometrically, they are rotations since they preserve distances.
Notation confusion: the books uses capital letters both for matrices and vectors.
P 71, tensor product of matrices.
p 80, doubly stochastic matrix.
Multiplying it by a vector of probabilities gives a vector of probabilities (i.e., they sum to 1 and $0\le a_i \le 1$ ).
P 88, Chapter 3, section 3.3 Quantum systems,
Real probabilities add.
When probabilities are norms of complex numbers, they might cancel.
p 91, Ex 3.2.2
p 93 double slit experiment
p 97 Section 3.4, Assembling systems
p 103 Chap Basic quantum theory
Feel free to read ahead.
https://en.m.wikipedia.org/wiki/Bloch_sphere:
The state of a qbit can be represented as a point on or in a sphere of radius 1.
E.g., |1> is the north pole, |0> the south pole.
Many operations are rotations.
Common operations (aka gates):
https://en.wikipedia.org/wiki/Quantum_logic_gate
Swap
controlled not CNOT cX
When input is general, it's more sophisticated that it looks.
Hadamard.
1-qbit creates a superposition.
https://cs.stackexchange.com/questions/63859/intuition-behind-the-hadamard-gate
2-qbit creates a uniform superposition
Toffoli, aka CCNOT.
Universal for classical boolean functions.
(a,b,c) -> (a,b, c xor (a and b))
Fredkin, aka CSWAP.
https://en.wikipedia.org/wiki/Fredkin_gate
3 inputs. Swaps last 2 if first is true.
sample app: 5 gates make a 3-bit full adder.
Bell state
Maximally entangled.
Hadamard then CNOT.
Algorithms:
Some, but not all, are faster.
Bounded-error quantum polynomial time (BQP)
"is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances" - https://en.wikipedia.org/wiki/BQP
Includes integer factorization and discrete log.
Relation to NP is unknown (big unsolved problem).
Searching problems:
Find the answer to a puzzle.
Math examples: factor an integer, solve a polynonial equation.
Testing validity of a putative solution is easy.
Finding that putative solution, naively, requires testing all possibilities.
Quantum computation can solve some searching problems faster.
This is probabilistic or noisy; often the found solution is wrong.
So you repeat the computation enough times that the error rate is acceptably low.
Some classical algorithms are similar. There is an excellent probabilistic primality algorithm.
The quantum algorithms are quite complex. (i.e., I'm still learning them.)
Algorithms, another view
Hadamard matrix rotates the pure state to an entangled superposition.
Then we operate in parallel on each state in the superposition.
Finally we separate out the desired answer.
Grover's algorithm:
Given a black box with N inputs and 1 output.
Exactly one input makes the output 1.
Problem: which one?
Classical solution: Try each input, T=N.
Quantum: $T=\sqrt(N)$.
Probabilistic.
Apps: mean, median, reverse a crypto hash, find collisions, generate false blocks.
Can extend to quantum partial search.
Grover's algorithm is optimal.
This suggests that NP is not in BQP .
Shor's algorithm:
Factorize an integer.
in BQP.
almost exponentially faster than best classical algorithm.
Largest examples I can find:
Table of contents
Any questions?
It's time to review some math fundamentals, from Quantum Computing for Computer Scientists. This will help with entanglement.
Read chapter 1 on your own; you should know it.
Chapter 2:
Complex vector space, page 34.
n-dim vector $\begin{vmatrix} c_0 \\ \cdots \\ c_{n-1}\end{vmatrix}$
Add 2 vectors.
Multiply vector by scalar.
etc.
Set of $m\times n$ complex matrices, $\mathbb{C}^{m\times n}$, is also a complex vector space.
Transpose, conjugate, adjoint.
Matrix mult is $\star$ in book.
$\mathbb{C}^{m\times n}$ is a complex algebra.
Set of polynomials in one variable of degree $le n$ is a complex vector space.
State of a quantum system is a complex vector.
You can make new vector spaces from combos of old ones.
Cartesian product or direct sum.
Just an ordered pair.
$(v_1, v_2)$.
Set of basis vectors for the vector space.
Every vector $v$ in the space is a linear combo of the basis vectors.
Represent $v$ as the list of weights.
There are many possible basis sets.
Each different basis set causes a different representation for the vectors.
Convert: change of basis.
Cartography example: NAD27, WGS84.
A bridge between Switzerland and Germany across the Rhine River at Laufenberg had its two ends at different elevations because of a conversion error between two different basis systems.
Hadamard matrix is an example.
Section 2.4 Inner product, etc, p 53 will be covered later.
Section 2.7 Tensor product of vector spaces, p 66.
$\mathbb{V} \otimes \mathbb{V'}$.
Let $dim(\mathbb{V})=p$ and $dim(\mathbb{V'})=q$ . Then $dim(\mathbb{V} \otimes \mathbb{V'}) = pq$.
This is how quantum systems combine.
Example 2.7.2 p 70.
Chapter 3 through 3.2, p 74-88.
State is a 4-vector of length 1.
It was originally created as the exterior product of two 2-vectors, the states of two separate 1-qbit systems.
Originally the separate 1-qbit systems didn't affect each other. Either could be transformed and measured.
Then 2-qbit system was rotated with a transformation matrix.
Now, perhaps it can be decomposed into the exterior product of two 2-vectors. Perhaps not.
Case 1: The 4-vector representing the new state can be decomposed.
Then it's still really two separate 1-qbit systems.
They can still either be transformed and measured.
Measuring one qbit does not affect the other qbit.
Case 2: The 4-vector representing the new state cannot be decomposed.
So the 2 qbits are now entangled.
That means that measuring one qbit affects what you will see when you measure the other.
It might just bias the probabilities of measuring the other qbit as 0 or 1.
Or, it might totally control what you will see.
Last time, there was a question about Asher Peres, Quantum Disentanglement and Computation, https://cds.cern.ch/record/330754/files/9707047.pdf
It's a matrix multiplication.
Due 2020-09-14 4:45pm in gradescope.
Quantum Computing for Computer Scientists will be very useful.
Ok to work in groups of 3 and submit one solution.
(2 points) Compute (1+2i)/(3+4i).
(5 pts) Compute the eigenvalues of $\begin{vmatrix} 1&2\\3&4 \end{vmatrix}$.
(2 pts) Considering complex numbers as points in the 2D plane, what is the geometric effect of multiplying a complex number by (.6+.8i) ?
(5 pts) Do exercise 1.3.8. Let c = 1 − i. Convert it to polar coordinates, calculate its fifth power, and revert the answers to Cartesian coordinates.
(5 pts) Exercise 1.3.9 Find all the cube roots of c = 1 + i.
(5 pts) Find the inverse Mobius transformation to
$$R_{a,b,c,d}(z) = \frac{az+b}{cz+d}$$
(5 pts) Invert the Hadamard matrix $\frac{1}{\sqrt{2}} \begin{vmatrix} 1&1\\1&-1\end{vmatrix}$.
(2 pts) Could a classical OR gate, with 2 inputs and 1 output, be a quantum gate? Why?
(2 pts) Could the following extension of a classical OR gate, with 2 inputs and 2 outputs, be a quantum gate? Why?:
A' = A or B B' = B
(2 pts) What about this extension of a classical XOR gate, with 2 inputs and 2 outputs. Can it be a quantum gate? Why?:
A' = A xor B B' = B
Total: 35
Table of contents
They are accessible from the Files tab on the top menu bar.
So far, they include scans of my handwritten notes during the lectures, and webex's attempt at a written transcript of the lecture videos. It's actually useful.
Let's try RPI's mediasite: https://mediasite.mms.rpi.edu/Mediasite5/Channel/quantum
Please ask questions. I try to have the chat window open most of the time. If I ignore you, ok to unmute your mike to ask a question.
Constructive opinions and comments are also welcome.
https://www.telegraph.co.uk/technology/2020/09/02/britain-must-act-fast-prevent-brain-drain-quantum-computing/ - good summary of programs around the world.
https://venturebeat.com/2020/09/02/xanadu-photonics-quantum-cloud-platform/
These are the ones I tried unsuccessfully to show in class 1.
A beginner's guide to quantum computing | Shohini Ghose https://www.youtube.com/watch?v=QuR969uMICM 10:04
https://www.youtube.com/watch?v=TAzZKAdX2Tw 10:56 more technical
Bit.
Its 2 possible values are 0 or 1.
Byte.
Has 8 bits.
It has 256 possible values.
Bits are transformed with gates, like nand, nor, and, or, xor, not, ...
They generally destroy info, and are not invertible.
More complex circuits, like adders, are formed from a combo of these gates.
Qbit, $q$.
Its state is a linear combo of two basis states, $|0>$ and $|1>$:
$q = a|0> + b|1>$ ,
where $a$ and $b$ are complex numbers, and $ | a | ^2 + | b | ^2 = 1$.
IOW, its state is a superposition of those two basis states, with those weights.
It is wrong to think that $q$ is really in one of the two states, but you don't know which one. This is the hidden variable theory. It has been proved experimentally to be false.
$q$ is really in both states simultaneously.
Alice laughed. "There's no use trying," she said: "one can't believe impossible things." "I daresay you haven't had much practice," said the Queen. "When I was your age, I always did it for half-an-hour a day. Why, sometimes I've believed as many as six impossible things before breakfast." - Through the Looking-Glass, and What Alice Found There (1871), by Lewis Carroll (Charles Lutwidge Dodgson).
You cannot observe its state, unless it is $|0>$ and $|1>$, in which case you observe $0$ or $1$. This is the classical case.
Otherwise you observe it with a measurement operator that transforms it to either $|0>$ and $|1>$, with probabilities
$| a | ^2$ and $| b | ^2 = 1$, respectively.
$a$ and $b$ are complex.
That measurement changes $q$; it no longer has its old value.
$q$, that is, $q$ 's value, can be considered to be a vector of length one: $$\begin{pmatrix} a | 0> \\ b | 1> \end{pmatrix} $$ or simply $$\begin{pmatrix}a\\b\end{pmatrix}$$.
You operate on $q$ with a matrix multiplication: $q_2 = M q$.
This changes $q$; the old value is no longer available.
No cloning: You cannot copy a qbit, but can move it.
The life cycle of a qbit:
Create a qbit with a classical value, 0 or 1.
Operate on it with matrices, which rotate it to have complex weights.
Transform it back to 0 or 1 and read it.
So far, not very powerful.
Now, let $q$ be a system with two qbits, i.e., a 2-vector of qbits.
Class 3 is on Tues Sept 8 because of Labor Day
Crazy counterintuitive idea that's the basis for quantum speedup.
Classical metaphor for entanglement:
Start with a piece of paper.
Tear it into two halves.
Put each half into an envelope, seal them, and mix them up, so that you can't tell which half is in which envelope.
Address and mail one envelope to a friend in Australia, and the other to a friend in Greenland.
When the Australian opens his envelope, he knows what the Greenlander will find in his.
However that doesn't let the Australian send any info to the Greenlander, or vv.
This has been demonstrated with real qbits transported 1000 miles apart.
Entanglement means that if you measure one qbit then what you observe restricts what would be observed when you measure the other qbit.
However that does not let you communicate.
Now, let $q$ be a system with two qbits, i.e., a 2-vector of qbits.
$q$ is now a linear combo of 4 basis values, $ | 00>$, $ | 01>$, $ | 10>$, $ | 11>$.
$q = a_0 | 00> + a_1 | 01> + a_2 | 10> + a_3 | 11> $
where $a_i$ are complex and $ \sum | a_i | ^2 = 1$.
$q$ exists in all 4 states simultaneously.
If $q$ is a vector with n component qbits, then it exists in $2^n$ states simultaneously.
This is part of the reason that quantum computation is powerful.
A measurement operator applied to $q$ will rotate it to a basis {00, 01, 10, 11}, so that it will be observed in one of those four cases, with probabilities $ | a_i | ^2$.
You operate on $q$ by multiplying it by a 4x4 matrix operator.
The matrices are all invertible, and all leave $ | q | = 1$.
You set the initial value of $q$ by setting its two qbits each to 0 or 1.
How this is done depends on the particular hw.
I.e., initially, $q_1 = \begin{pmatrix}a_1 | 0> \\b_1 | 1> \end{pmatrix}$ and $q_2 = \begin{pmatrix}a_2 | 0> \\b_2 | 1> \end{pmatrix}$, and so
$$q = \begin{pmatrix} q_1 \\ q_2 \end{pmatrix} = \begin{pmatrix} a_1 a_2 | 00 > \\ a_1 b_2 | 01 > \\ a_2 b_1 | 10 > \\ b_1 b_2 | 11 > \end{pmatrix}$$.
Here, the combined state is the tensor product of the individual qbits.
For $n$ qbits, the tensor product is a vector with $2^n$ elements, one element for each possible value of each qbit.
Each element of the tensor product has a complex weight.
You transform a state by multiplying it by a matrix.
The matrix is invertible.
The transformation doesn't destroy information.
When you measure a state, it collapses into one of the component states. (This may be inaccurate.)
You don't need to bring in consciousness etc. The collapse happens because the measurement causes the state to interact with the outside world.
The probability of collapsing into a particular state is the squared magnitude of its complex weight.
For some sets of weights, particularly after a transformation, the combined state cannot be separated into a tensor product of individual qbits. In this case, the individual qbits are entangled.
That is the next part of why quantum computation is powerful.
Entanglement means that if you measure one qbit then what you observe restricts what would be observed when you measure the other qbit.
However that does not let you communicate.
From page 171 of
Quantum Computing for Computer Scientists 1st Edition
All quantum algorithms work with the following basic framework:
The system will start with the qubits in a particular classical state.
From there the system is put into a superposition of many states.
This is followed by acting on this superposition with several unitary operations.
And finally, a measurement of the qubits.
Ways to look at measurement:
Converts qbit to classical bit.
Is an interaction with the external world.
Information is not lost, but leaks into the external world.
Is an operator represented by a matrix.
that is Hermitian, i.e., it's equal to its complex transpose.
For physical systems, some operators compute the system's momentum, position, or energy.
The matrix's eigenvalues are real.
The result of the operation is one of the eigenvalues.
More from
Quantum Computing for Computer Scientists 1st Edition
Compare byte with qbyte.
State of byte is 8 bits.
State of qbyte is 256 complex weights.
They all get modified by each operation (aka matrix multiply).
That is the power of quantum computing.
The current limitations are that IBM does only a few qbits and that the operation is noisy.
Table of contents
Read the syllabus, accessible from the top bar.
This term we will be using Piazza for class discussion. It is widely used at RPI. The system is catered to getting you help fast and efficiently from classmates and myself. Rather than emailing questions, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com.
I (WRF) have added everyone enrolled as of 8/30. Anyone else can add yourself at the class signup link at: https://piazza.com/rpi/fall2020/ecse4964 .
We'll use Gradescope for submitting homeworks and possibly projects. I've added everyone as of 8/30.
I do parallel geometry algorithms on large problems for CAD and GIS. See my home page. If this is interesting, talk to me. Maybe you can do something that leads to a jointly-authored paper.
