Spring 2026
Practice Assignment - 1
Quantum Computing: Algorithms and Limitations Through the Query Model
Objective: Assess understanding of the prerequisites for the course.
• Please read each exercise carefully.
• Every item on the test awards 2 points for each correct answer, for a maximum
possible score of 20 points.
• You don’t need calculator for this examination.
• Mere suspicion of cheating, sharing calculators or using any unfair means of aid
is enough to get your test withdrawn.
Suppose there is an imaginary insect (named Ro), which might have a ring on its body.
Whether Ro will have a ring or not is dependent on its parents. Specifically, Ro will have a
ring on its body if and only if one of its parents have a ring.
Let us assume that there is an injection, which changes whether the insect has a ring or
not. That is, an insect with a ring will not have a ring after it gets an injection. On the
other hand, an insect without a ring will get a ring after the injection.
Then, answer the following questions based on the above provided information.
1. (MCQ) What computation does the following figure (Figure 1) accomplish?
Figure 1: Some Insect-Based Computations
A. OR AND(a, b), AND(c, d)
B. OR AND a, NOT(b) , AND c, NOT(d)
C. OR AND NOT(a), b , AND c, NOT(d)
D. OR OR NOT(a), b , OR c, NOT(d)
E. AND AND NOT(a), b , AND c, NOT(d)
F. AND OR(a, b), OR(c, d)
Solution: Follows from definition.
2. (MCQ) What computation does the following figure (Figure 2) accomplish?
Figure 2: Some More Insect-Based Computations
A. OR OR(a, b), AND(c, d)
B. OR AND NOT(a), NOT(b) , AND c, d
C. OR AND a, b , AND NOT(c), NOT(d)
D. OR OR NOT(a), b , OR c, NOT(d)
E. AND AND(a, b), OR(c, d)
F. OR AND(a, b), OR(c, d)
Solution: From De Morgan’s Law from Boolean Algebra, we have
NOT OR(NOT(a), NOT(b)) = AND(a, b).
The rest follows from definition.
3. (MCQ) The fundamental difference between quantum and classical computers is
A. quantum computers use qubit, classical computers use bit
B. quantum computers can store infinite information in one bit
C. quantum computers can make all computations much faster than classical com-
puters
D. quantum computers use quantum mechanical properties of the sys-
tem to do computation
E. classical computers do not follow the rules of quantum mechanics
F. classical computers can not simulate quantum computers
Solution: Recall.
4. (MCQ) What is the Church-Turing hypothesis?
Page 2
A. Any function can be computed by a Turing machine.
B. Any function can be computed by a Turing machine in time polynomial in the
size of the input to the function.
C. Any function computable by any machine is also computable by a
Turing machine.
D. Any function computable by any machine is also computable by a Turing
machine in time polynomial in the size of the input to the function.
Solution: Recall.
5. (MSQ) Which of the following is/are correct?
A. The Church-Turing Hypothesis states that the class of all com-
putable problems is independent of the model of computation.
B. The Strong Church-Turing Hypothesis states that the class of all
efficiently solvable problems is independent of the model of compu-
tation.
C. Quantum Computers are strong candidates against the validity of the Church-
Turing Hypothesis.
D. P = NP under a quantum computer.
Solution: We say that a problem can be efficiently solved if it belongs to the class
of problems P. Given that, recall the Church-Turing Hypothesis, the Strong Church-
Turing Hypothesis, and how quantum computers are potential candidates challenging
the later. Also, till date, there does not exist any example NP − Complete problem
which is known to be efficiently solvable on a quantum computer.
6. (MCQ) The output of any randomized/probabilistic algorithm
A. depends solely on the input x ∈ {0, 1}∗ to the algorithm.
B. depends on the input x ∈ {0, 1}∗ to the algorithm, and a qubit q ∈ H2 .
C. depends solely on a random string r ∈ {0, 1}∗ .
D. depends on the input x ∈ {0, 1}∗ to the algorithm, and a random
string r ∈ {0, 1}∗ .
Solution: Recall.
7. (MCQ) Two different waves when superpositioned (i.e., when they overlap) can undergo
A. constructive interference.
B. destructive interference.
C. both constructive as well as destructive interference.
D. only constructive or destructive interference, but not both.
Solution: Some of the waves’ components might undergo constructive interference,
while some might undergo destructive interference.
8. (MSQ) For the Mach-Zehnder Interferometer given in Figure 3, which of the following
option(s) is/are true?
Page 3
Figure 3: Mach-Zehnder Interferometer
A. When the photon gun is fired, only one of the detectors lights up.
B. When the photon gun is fired, both of the detectors start lighting up with
probability 21 .
C. If we block one of the photon paths (remove one of the mirrors or
place an obstruction), both detectors start lighting up with proba-
bility 12 .
D. If we block one of the photons paths (remove one of the mirrors or place an
obstruction), one of the detectors never lights up.
Solution: Recall.
9. (MSQ) For the Elitzur-Vaidman bomb tester setup given in Figure 4, which of the
following option(s) is/are true?
Figure 4: Elitzur-Vaidman Bomb Tester
A. If the bomb is a dud, then we will always observe the photon at
Detector 1.
B. If the bomb is real, then we will always observe the photon at Detector 2.
1
C. If the bomb is real, then with probability 4
we incorrectly call it a
dud.
D. If the bomb is real, then it will explode with probability 12 .
Page 4
Solution: Recall.
10. (MCQ) The experiment of Mach-Zehnder interferometer shows that
A. a quantum computer is same as a probabilistic computer.
B. the amplitudes being negative does not give power to a quantum computer.
C. the amplitudes being negative give rise to surprising results in qua-
tum devices.
D. a quantum computer is same as a parallel computer.
Solution: Recall.
Page 5