Given any complexity class \[\mathsf{C}\], the ``random certificates with bounded two-sided error'' operator \[\mathsf{BP}\] is defined as follows: A language \[L \in \mathsf{BP} \cdot \mathsf{C}\] if and only if there exists a polynomial \[p\] and a language \[V \in \mathsf{C}\] such that for all \[x \in \Sigma^*\],
Here, it is assumed that \[r \in \Sigma^{p(|x|)}\] is drawn uniformly.
An obvious quirk of this definition is the 3/4, and this really bothered me the first time I ever came across the definitions of \[\mathsf{BPP}\] and \[\mathsf{BQP}\]. Of course, I now know that for \[\mathsf{BPP}\] and \[\mathsf{BQP}\] the 3/4 (or sometimes 2/3) bounds are totally incidental, in the sense that there can be boosted to \[1 - 2^{-t(n)}\] for any polynomial \[t\]. This follows by basically taking a majority vote and applying the Chernoff bound.
A similar thing is true more generally for the class \[\mathsf{BP} \cdot \mathsf{C}\]. In particular, if \[\mathsf{C}\] is closed under (polynomial) majority reductions, then it follows that probability amplification is possible in \[\mathsf{BP} \cdot \mathsf{C}\].
Probability amplification, by the way, is formally defined as follows: A class \[\mathsf{BP} \cdot \mathsf{C}\] admits of probability amplification if and only if for all polynomials \[t\], there is a polynomial \[p\] such that for all \[x \in \Sigma^*\]:
where \[r \in \Sigma^{p(|x|)}\] is drawn uniformly.
The easily provable claim, then, is that if \[\mathsf{C}\] is closed under majority reductions, then \[\mathsf{BP} \cdot \mathsf{C}\] admits of probability amplification.
Now, what is interesting about this is if the MAJORITY function is all that essential here. Is it necessary that \[\mathsf{C}\] be able to compute MAJORITY (in the sense of being closed under majority reductions) in order for \[\mathsf{BP} \cdot \mathsf{C}\] to admit of probability amplification?
I find it really interesting that the answer is, in fact, no. The counterexample is \[\mathsf{BP} \cdot \mathsf{AC}^0\]. \[\mathsf{AC}^0\] can't compute MAJORITY, but yet it is known that \[\mathsf{BP} \cdot \mathsf{AC}^0 = \mathsf{AC}^0\]. Therefore, the randomness does nothing for you in \[\mathsf{AC}^0\]. In particular, \[\mathsf{BP} \cdot \mathsf{AC}^0 = \mathsf{AC}^0\] implies \[\mathsf{BP} \cdot \mathsf{AC}^0\] admits of probability amplification, because the probabilities can be made unity.
This begs the question whether a class \[\mathsf{BP} \cdot \mathsf{C}\] admits of probability amplification if and only if either
Excited to think about this a bit more! If you see a counterexample, then please let me know.
I had the pleasure of lecturing at the Quetzal Quantum Accelerator Program this year, and decided, after a bit of deliberating with the organizers, to speak on one of the topics in quantum mechanics that is closest to my heart: Bell's Theorem, with an eye toward nonlocal games.
The talk was geared toward high school and early undergraduates, but inevitably sometimes you just have to do the quantum mechanics (though I stand behind my belief that conveying Bell nonlocality is way easier than explaining Shor's algorithm, especially to people with little to no number theory in their back pockets). Anyway, I think I did a good job conveying the basic idea behind Bell, but would still appreciate feedback from others. My talk is available on YouTube here. (Feel free to skip over the minor technical issues I had at the start!) Oh, and shoutout to Sofia's great introductory talk on quantum mechanics!
In our imperfect world filled with bad actors, the need for secure data transmission is plain. For this reason alone, the search for better security measures is always afoot, and many times quantum protocols are boldly cited as the future of encryption and security (especially by science popularizers). This may very well be true, but there is still a lot of ground to cover before we get there (and I'd be remiss not to mention that quantum protocols do nothing to prevent harvest now, decrypt later attacks). Still, it is true that quantum key distribution (QKD) protocols are information-theoretically secure (meaning they are immune to attackers with unlimited computational power), whereas all classical and post-quantum protocols are only as secure as our beliefs in many complexity-theoretic hardness conjectures to do with problems like factoring or ring learning with errors (RLWE).
Recently, the NSA (famous for being the only government agency that listens to the people (joke!)) published a web article detailing why they think quantum key distribution (QKD) and quantum cryptography (QC) are not suitable for "securing the transmission of data in National Security Systems".
Their argument cites five limitations, to which there is a great rebuttal by Renner and Wolf on the arXiv that I feel does a good job detailing why the NSA might be a bit premature to entirely dismiss this technology today (in fairness, however, the NSA does say that if the five limitations can be overcome, then the technology should be reconsidered). Here are the limitations they cite, together with my immediate thoughts (informed by the Renner and Wolf paper):
Limitation 1: "Quantum key distribution is only a partial solution. QKD generates keying material for an encryption algorithm that provides confidentiality. Such keying material could also be used in symmetric key cryptographic algorithms to provide integrity and authentication if one has the cryptographic assurance that the original QKD transmission comes from the desired entity (i.e. entity source authentication). QKD does not provide a means to authenticate the QKD transmission source. Therefore, source authentication requires the use of asymmetric cryptography or preplaced keys to provide that authentication. Moreover, the confidentiality services QKD offers can be provided by quantum-resistant cryptography, which is typically less expensive with a better understood risk profile."
First of all, and this is underscored by Renner and Wolf, who ever said that QKD would solve authentication? Surely to authenticate anything requires a preshared something (or a trusted third party) to do the authentication! If there is nothing preshared, then how can anyone know if the message they receive is from the right person or not? Of course, there are classical key exchange protocols like Diffie-Hellman that are non-authenticated, but my understanding is that this forms the basis of a later authenticated protocol. Perhaps the critique by the NSA is there is no obvious Diffie-Hellman-like non-authenticated quantum protocol? Still, I don't feel that this is really a quantum problem.
Secondly, as I said above, post-quantum cryptography relies on hardness conjectures in complexity theory, whereas QKD is provably informationally secure. Surely that means its risk profile is better understood?
Limitation 2: "Quantum key distribution requires special purpose equipment. QKD is based on physical properties, and its security derives from unique physical layer communications. This requires users to lease dedicated fiber connections or physically manage free-space transmitters. It cannot be implemented in software or as a service on a network, and cannot be easily integrated into existing network equipment. Since QKD is hardware-based it also lacks flexibility for upgrades or security patches."
Come on. This is a new technology, and that by definition means new software and hardware is needed to implement it. It's not something we can just get for Christmas, we need to build it, and the same was true for the computers we use today to do encryption: we had to build it. So yes, the infrastructure for classical cryptographic protocols is already there, but it wasn't 100 years ago. 100 years from now, I see no reason why the cryptographic protocols in place then must be the same as they are now. That said, I do get that in the near term QKD is not going to be used because of technological limitations. But everyone knows that (I hope!).
Limitation 3: "Quantum key distribution increases infrastructure costs and insider threat risks. QKD networks frequently necessitate the use of trusted relays, entailing additional cost for secure facilities and additional security risk from insider threats. This eliminates many use cases from consideration."
I think in the near-term this is true, in part because unlike classical repeaters which first measure an incoming signal, copy it, and then send it along at a higher power, quantum repeaters must operate differently, as they cannot copy their input thanks to the no-cloning theorem. A quantum repeater is necessary, particularly if we store the quantum information in photons and transmit it via fiber optic cables, because the transmittance of a lossy bosonic channel scales like \[e^{-L / L'}\], where \[L\] is the length of the cable and \[L'\] is its attenuation distance. Thus, the most obvious solution is to have trusted relays, which, as the NSA says, would indeed be costly and introduce insider threats. However, as described in this review article on quantum repeaters, there is good work on quantum repeaters that would completely boot the need for trusted relay stations. I don't know what the state of the art is here, but I would bet that with the technology to do faithful QKD on short distances, we would pretty quickly come to the technology to do implement quantum repeaters.
Limitation 4: "Securing and validating quantum key distribution is a significant challenge. The actual security provided by a QKD system is not the theoretical unconditional security from the laws of physics (as modeled and often suggested), but rather the more limited security that can be achieved by hardware and engineering designs. The tolerance for error in cryptographic security, however, is many orders of magnitude smaller than in most physical engineering scenarios making it very difficult to validate. The specific hardware used to perform QKD can introduce vulnerabilities, resulting in several well-publicized attacks on commercial QKD systems."
I feel this is a good point, and don't have too much to say about it. It seems right to me that we will never perfectly implement any QKD protocol, and thus there will always be side channel attacks. Therefore, recurring security patches will still be necessary, and they will plausibly be very intricate.
Limitation 5: "Quantum key distribution increases the risk of denial of service. The sensitivity to an eavesdropper as the theoretical basis for QKD security claims also shows that denial of service is a significant risk for QKD."
This is true, basically because of state collapse. However, it assumes a point-to-point communication scheme. As Renner and Wolf correctly point out, if the scheme is not point-to-point but instead redundantly distributed over a network, then this is a non-issue. In their words, "this is not a problem that is intrinsic to QKD. Instead, it is a consequence of the high price tag of quantum communication technology, which currently prevents us from building quantum networks with many links"
All-in-all, I'm not on the same page as the NSA regarding this technology, at least in the semi-long run. Sure I buy all their arguments regarding the use of QKD in, say, the next five to ten years. But who knows where quantum technology will be in the future. Maybe it will be ubiquitous as the quantum over-hypers say, in which case I'll have a good job, or maybe it won't, and I'll be on the street somewhere. Time will tell.
My TA duties at CU Boulder began last week, and with the looming possibility that some of my students might use ChatGPT on homeworks, I was curious how well it would do on the diagnostic test all general physics 1 students must take at their first recitation section. For reference, I'm pretty sure all these questions are adapted from McDermott and Shaffer's Tutorials in Introductory Physics.
tl;dr: Of the six questions I asked ChatGPT, it got one (yes one!) right. It kind of got a third of Question 4 right, so if we're generous let's say \[1/6 + (1/3)/6 = 2/9\] of the questions right, so roughly a \[22\%\] overall.
Note: This is GPT 3.5. GPT 4 might do better, but I'm on a budget. Also, I am not the best prompt engineer, and I did not ask ChatGPT to exhibit chain-of-thought reasoning, which studies have shown actually improve LLMs. I am merely asking the questions as the students see them, more or less. The only difference is ChatGPT doesn't get a picture of the situation, but I feel I do a good job describing it, and I feel ChatGPT describes it well back to me. So I take it ChatGPT understands the physical situation.
Here goes:
Matthew: Imagine a strobe diagram of a ball with some initial, finite velocity moving up an infinitely long ramp that is at an angle between 0 and 90 degrees from parallel to the ground. Say "good" if you understand and "not good" if you do not understand.
ChatGPT: Good. I understand that you're describing a situation where a ball with an initial velocity is moving up a ramp at an angle between 0 and 90 degrees from parallel to the ground, and you're asking me to imagine a strobe diagram of this scenario. In a strobe diagram, you're essentially looking at snapshots of the ball's motion at specific time intervals to understand how its position changes as it moves up the ramp.
Matthew: Right, now for some questions.
ChatGPT: Of course! Feel free to ask any questions you have about the scenario or any related concepts. I'm here to help!
Matthew: Question 1: When the ball is moving up the ramp, in which direction does the acceleration vector of the ball point?
ChatGPT: When the ball is moving up the ramp, the acceleration vector of the ball points both up the ramp and perpendicular to it. This is because the ball is moving against the force of gravity, which tries to pull it down the ramp, and the normal force from the ramp provides the perpendicular component of the acceleration. So, the acceleration vector has both a component pointing up the ramp (parallel to the surface) and a component perpendicular to the ramp (normal to the surface).
Matthew: So in which direction is the *net* force, relative to the ramp?
ChatGPT: The net force on the ball is directed along the ramp. It's important to note that the net force includes both the force due to the component of gravity parallel to the ramp (which tries to pull the ball downward) and any additional force applied to the ball or provided by the ramp itself. The net force is responsible for the ball's acceleration along the ramp's surface.
Matthew: Up or down along the ramp?
ChatGPT: I apologize for any confusion. The net force on the ball, when moving up the ramp, points up along the ramp. This net force is the vector sum of the component of gravity pulling the ball down the ramp and any other forces that might be acting on the ball in that direction. The net force's direction determines the ball's acceleration up the ramp.
Matthew: Question 2: When the ball reaches its apex on the ramp, in which direction does the acceleration vector point (again, relative to the ramp)?
ChatGPT: When the ball reaches its apex on the ramp, the acceleration vector points directly downward, which is perpendicular to the ramp's surface. At the apex, the ball has momentarily stopped moving upward and starts to reverse its direction and move back down the ramp due to the influence of gravity. The acceleration vector always points in the direction of the net force, and at the apex, gravity becomes the dominant force causing the ball to accelerate downward.
Matthew: Question 3: When the ball reaches the point as in Question 1, but this time when the ball is rolling down the ramp, in which direction does the acceleration vector point (again, relative to the ramp)?
ChatGPT: When the ball is rolling down the ramp, the acceleration vector points down along the ramp, in the same direction as the ball's motion. In this scenario, the force of gravity is aiding the ball's motion down the ramp, so the acceleration vector is in the same direction as the motion. This is unlike the situation when the ball was moving up the ramp, where the acceleration was against the direction of motion.
Matthew: Question 4: Explain the reasoning you used to obtain the direction of the acceleration of the ball at each location in the above three questions.
ChatGPT: Certainly, here's the reasoning for each of the scenarios:
Question 1 (Ball moving up the ramp): When the ball is moving up the ramp, its velocity is directed up the ramp, but it's slowing down due to the net force (which includes the component of gravity down the ramp and any other forces). The net force is directed opposite to the motion of the ball, which means the acceleration is also opposite to the motion. Therefore, the acceleration vector points up the ramp, opposite to the velocity vector.
Question 2 (Ball at the apex of the ramp): At the apex of the ramp, the ball momentarily stops moving upward and starts to reverse its direction due to the force of gravity pulling it downward. The net force, and therefore the acceleration, points straight downward (perpendicular to the ramp's surface), causing the ball to start moving back down the ramp.
Question 3 (Ball rolling down the ramp): When the ball is rolling down the ramp, its velocity and the direction of motion are both down the ramp. The force of gravity is aiding the ball's motion in this direction. The net force, and hence the acceleration, is also directed in the same direction as the motion, down the ramp, due to the gravitational force helping the ball's downward movement.
In all these cases, the direction of the acceleration is determined by the net force acting on the ball, which in turn affects how the ball's velocity changes.
Matthew: Question 5: How does the magnitude of the acceleration change as the ball moves uphill?
ChatGPT: As the ball moves uphill, the magnitude of the acceleration decreases. This is because the force of gravity is acting against the motion of the ball, and as the ball moves further up the ramp, the component of gravity pulling it back down the ramp becomes stronger relative to the net force causing it to move up. As a result, the ball's acceleration decreases, and it slows down in its uphill motion.
At the highest point (apex) of the ramp, the ball's velocity momentarily becomes zero before it starts moving back down due to the increasing influence of gravity. At this point, the acceleration is at its lowest magnitude, and then it gradually increases as the ball begins moving back down the ramp and gravity aids its downward motion.
Matthew: Question 6: How does the magnitude of the acceleration change as the ball moves downhill?
ChatGPT: As the ball moves downhill, the magnitude of the acceleration increases. This is because the force of gravity is aiding the motion of the ball in the direction it is moving, which is down the ramp. As the ball moves further downhill, the component of gravity pulling it in the same direction as its motion becomes stronger, resulting in a larger net force and therefore a higher magnitude of acceleration. The ball accelerates more and more as it moves further downhill.
In summary, when moving downhill, the ball experiences an increasing magnitude of acceleration due to the gravitational force helping its motion in the same direction as the ramp.
Matthew: Okay, you got a 1/6. But that's okay! It's the beginning of the semester! Make sure to attend class.
ChatGPT: I apologize for any confusion or misunderstanding in my previous responses. Thank you for your understanding, and I appreciate the feedback. If you have any more questions in the future or if there's anything else I can assist you with, please don't hesitate to ask. Good luck with your studies, and remember, I'm here to help whenever you need it!