February 11, 2005
Quantum Computing Group
“More resumes for you, Dr. Peterson,” Mona said to Rick, as she placed seven resumes onto the tall stack of hundreds of resumes already on his desk.
“Thanks babe,” he called to Mona as she walked away.
Rick licked his lips as he stared at Mona’s butt in her tight black skirt. He looked over at Michael sitting across from him, also staring at Mona. Rick reached out to fist bump Michael.
“She’s looking smoking today, isn’t she Mike?” Rick asked.
“Yeah man, she really is,” Mike said.
With his legs up on his desk and leaning back in his chair, Rick glanced through the newest resumes. In the past year, he’d looked through thousands of interviews and held dozens of interviews, only finding a couple applicants to hire as software engineers in his Quantum Computing Group at MIT.
The first resume was from an MIT senior majoring in electrical engineering, who had done research in the systems group at MIT, and worked on systems at Google as a software engineer intern for the past two summers. He glanced up at the name, Kelsey. He shook his head and placed the resume in the rejection pile.
Veronica, next. Sophia, next. Jill, next. Julia, next.
After looking through some more resumes, the only good resume Rick found was that of Jordan Harris, a computer science and physics double major at MIT. Jordan had a 3.95 GPA and previously worked in the systems group at MIT.
Rick dialed Mona’s number. “Mona, schedule an interviews for me with Jordan Harris tomorrow.”
Rick loved the culture he’d built at the Quantum Computing Group. With Beer Fridays, hackathons, and heavy-duty science, this wasn’t a place for women. Mona already distracted Rick and the rest of the team from their work. He’d never met a female who could actually code.
February 12, 2005
Jordan glanced at her alarm clock. It was 4 a.m. and still dark outside, and she’d only slept a few minutes throughout the night. Her interview was later in the day, and she couldn’t stop thinking about how nervous she was.
Jordan didn’t think deserved a spot in the Quantum Computing Group. It was the most reputable group on campus. QCG was working on building a quantum computer and was led by the renowned Dr. Richard Peterson.
Realizing she wouldn’t fall back asleep, Jordan opened her laptop to do more research on QCG. She typed “Richard Peterson” into Google, and found his Wikipedia page. Dr. Peterson received his undergraduate degree in physics from the University of Mississippi, and didn’t hold any graduate degrees. He was most known for his discovery of the qubit and later for founding QCG.
Jordan was very familiar with the qubit from her physics coursework. She learned that typical computers process data in the form of bits, which can either be 0 or 1. A qubit, on the other hand, can hold the values 0, 1, or any quantum superposition of the two states. Two qubits could represent the superposition of four states, and three could represent eight states. In general, 2n states could be represented by only n qubits. This qubit was the basis for quantum computing.
She opened the “About” page on QCG’s and noticed that all eight engineers were from MIT or Harvard with majors in physics, computer science, and engineering. They were all men, but that was unsurprising to Jordan since this was MIT after all.
September 4, 2002
Intro to Computer Science lecture
Jordan arrived fifteen minutes before her first class and grabbed a seat in the front row, in between two male students.
She could see them smirking to one another from their corner of their eye.
“English class is down the hall, honey,” one of them said.
Jordan pretended not to hear them.
November 15, 2002
Intro to Computer Science lecture
“Damn, I got a C, what about you Spencer?” said the student to her left.
“C-,” Spencer said.
The teaching assistant dropped Jordan’s test on her desk. She got an A+.
“Damn Jordan, did your boyfriend take the test for you again?” Spencer asked.
“Got lucky, I guess,” she said.
Jordan had received almost perfect scores on all of her computer science assignments throughout the semester.
Four more years, she thought.
February 12, 2005
Quantum Computing Group
“I’m here for a 2:30 interview with Dr. Richard Peterson,” Jordan said to the secretary at the front desk of QCG.
“And you are?” Mona asked.
Mona looked Jordan up and down, noting her glasses, slender body frame, and shy demeanor.
“Have a seat,” Mona said to Jordan.
Jordan sat in a chair in the corner, noting the newspaper and magazine clippings hanging on the walls. “QCG receives more funding”, “QGC hires big-time engineer from Google”, “QGC closer to building the next quantum computer.” She counted more than twenty photos of Dr. Peterson.
Mona dialed Rick’s number.
“Jordan is here for the interview. Should I send her in?” Mona said.
“Her?” Rick asked.
“What do you want me to do?”
“From now on I’m listing ‘male’ on the job description. Tell her to grab me a double shot espresso and send her in.”
“Sure,” Mona said, and hung up the phone.
“Jordan, please get an espresso from next door for Rick. There’s a Starbucks four blocks down,” Mona said, and handed Jordan a five-dollar bill.
“Won’t be the last,” Mona whispered under her breath, as Jordan walked away.
On her way to Starbucks, Jordan prepared herself for meeting this man. She was angry that he made her get coffee for him, but this position was an opportunity of a lifetime for her career. QCG was the most respected quantum computing lab in the world. Working there and getting a recommendation from Dr. Peterson would get her into any graduate computer science program in the world.
She thought back to her high school math teacher, who really took an interest in her and wrote her a glowing recommendation for MIT. And to the only other female in her classes, Audrey, who helped Jordan get through those twenty-plus hour problem sets. And to her mom, who worked two jobs to support her college tuition after her dad left when she was fifteen.
MIT, A’s in her classes—Jordan didn’t believe she deserved any of those. With graduate school applications due next year, she needed something that would stand out and somehow show that she deserved to get into top schools.
Jordan was nervous but ready to meet Dr. Peterson. Fetching espressos is a small price to pay for such an incredible opportunity.
“Are you working on any side projects, Jordan?” Rick asked, yawning.
“Well besides my engineering and physics classes, I’m working on a problem that could make the shipping industry more efficient,” Jordan explained. “The problem is this. Consider a mailman who must deliver packages to a list of homes, and wants to minimize the amount of time spent delivering the packages. He needs to find the most efficient route in order to visit every home. As far as I know, no one has solved this problem.
“But I think I’m getting somewhere. As you must know, in computer science, a graph is a set of vertices V and edges E that connect the vertices. A weighted graph is a graph where the edges have weights. In this problem, the vertices are the delivery addresses, and the edges represent the distances between each address.
“I want to use this graph representation to find the shortest path from the mailman’s starting point and back again. Finding the shortest path between any two points already has an efficient algorithm called Dijkstra’s algorithm, which runs pretty quickly on any computer. The only difference here is that our path needs to contain all points.”
Jordan walked to the board to draw a demonstration of Dijkstra’s algorithm.
Damn, Rick thought. Jordan has a really nice ass. I don’t know who this Dijkstra is or what the point of this problem is. Also it’s cute that she thinks I would admit a girl into my lab. She does have nice legs though, I’d love to…
“And that’s Dijkstra’s algorithm,” Jordan said as she turned around. “Anyway, I’m getting closer to a solution that will solve the mailman problem in about the same amount of time as Dijkstra’s algorithm. I haven’t told anyone about this problem yet, but I think it could be worth something to Amazon, UPS, or something.”
“Thanks Jordan, we’ll be in touch.”
“How was your interview with Jordan?” Dennis, one of the lead engineers, asked Rick after the interview.
“Jordan was a chick, she wouldn’t fit in here. I’m going to tell Mona to send her a rejection email,” Rick said and started dialing Mona’s number.
“What did you talk about?” Dennis asked.
“She was rambling on about some guy named Dijkstra and some problem about a mailman delivering packages faster,” Rick explained. “Apparently no one knows the fastest way for delivery.”
“Does she have a solution?”
“Not yet, but she said she’s working on something that would solve it as fast as Dijkstra’s algorithm.”
“That’s a huge open problem in computer science.”
“Why do I care about this?” Rick asked. “Quantum computing is hot right now, let’s not lose focus.”
“This is much bigger than quantum computing. Once we finish this quantum computer, everyone is going to want to use it for decryption, since, as you of all people know, the qubits used in quantum computers will allow integer factorization to be computed efficiently, breaking current public-key encryption mechanisms like RSA. But none of this will matter if Jordan’s algorithm works.”
“How are these problems related, though?” Rick asked.
“From what you said it seems like Jordan doesn’t know this, but she’s solving a famous problem in computer science called the Traveling Salesman Problem. Given a list of cities and the distances between each of them, the problem asks for the shortest possible path for a salesman to travel from city to city, visiting every city on the list.
“The Traveling Salesman Problem is NP-complete, which is type of problem in computer science that cannot be solved in a reasonable amount of time by computers. These problems are intractable because solving them requires exponential time with classic computers. For a large problem size, the problems blow up and there isn’t enough computing power. There are a long list of problems which are known to be NP-complete, and some of them include: coloring a graph so that no adjacent vertices have the same color, finding the longest path in a graph, and even solving popular games such as Super Mario Bros and Candy Crush.
“None of these problems are known to have polynomial time solutions. If there did exist a polynomial time solution to any one of these problems, then there would be a polynomial solution to all of the problems. In other words, finding an efficient algorithm for one problem in this list would mean that all NP-complete problems can be solved.
“On this list of NP-complete problems are several methods used for encryption to prevent decryption. Quantum computers are one way to break certain types of encryption. But some encryption is based on NP-complete problems, which everyone believes are impossible to solve efficiently. If Traveling Salesman can be solved efficiently, then decryption of many encryption techniques would also be possible,” Dennis finished.
“Good thing one of us has a CS degree,” Rick laughed. “So how would this affect our development of quantum computers for decryption purposes?”
“Well, if decryption can be performed in polynomial time with regular computers, then people will be less interested in using quantum computing for decryption. As you know, the technology isn’t there yet, and it’s going to take some time,” Dennis explained.
Rick knew this could be bad news for QCG. They’d lose funding from the big guys like NSF, and they’d lose the talented scientists and engineers who want to be a part of the next big thing in computer science, which would be working on applications of NP-complete problems.
“I guess she’s hired,” Rick sighed. “Call Mona for me.”
February 13, 2005
Quantum Computing Group
“We have an open layout in the office, so all the engineers sit together. This helps with collaboration among the engineers,” Mike explained to Jordan, as he gave her a tour of the office.
Everyone sat in front of dual-screen MacBook Pros. There were two rows of four desks, with the rows facing each other. Four of the eight engineers sat at their desks coding away.
“That’s Stephan and Jake over there playing Ping Pong. On Fridays it turns into a Beer Pong table and everyone plays together,” Mike explained.
“Sounds fun,” Jordan murmured.
“Don’t play Beer Pong?” Mike asked.
“Not really my thing,” Jordan responded.
“Well that over there is Rick’s office,” Mike said, pointing to the closed glass door. “He also has a desk with us, but usually holds meetings in his office. There isn’t much room at the desks, so you’ll have to sit in the office down the hall. That’s okay though, because you won’t be working with us anyway.”
“What do you mean?” Jordan asked.
“Well, Rick figured that since you already have a problem that you’re working on, you can start out just working on that, and then when you finish maybe you can work with us on the quantum computer.”
“But I applied for this position because I wanted to work in quantum computing.”
“Well, to be honest, it didn’t seem like you had the engineering experience yet, but maybe we can revisit that in a few months after your problem is done.”
March 3, 2005
Quantum Computing Group
After Friday night beer pong, Jordan stayed to work on the mailman problem in her office.
“What are you still doing here?” Rick asked Jordan.
“Trying to code up the solution to the mailman problem. I think I have something. Watch.”
Rick leaned over Jordan’s shoulder as she typed into her terminal:
java Mailman cities.txt
This would compile the newest version of the Java program, and run it on a test list of cities, which was contained in the file cities.txt.
“cities.txt contains 5,000 cities and their distances to one another. An algorithm running in exponential time wouldn’t ever terminate.”
In 15 seconds, the program was complete, and Jordan’s terminal read
Cambridge: 0.0 mi
Brookline: 2.3 mi
Newton: 5.9 mi
Boston: 9.6 mi
The program listed the shortest path for the mailman to take in order to visit all of the cities, starting with Cambridge, the location of MIT.
Holy shit, Rick thought. Jordan has no idea what this is worth.
“Looks good,” Rick said. “You should go home for the night and enjoy the weekend.”
Jordan nodded and walked home.
Once Jordan left, Rick walked back into her office to send the program to himself and called Mike.
“Mike, Jordan’s code works,” Rick said. “Come to the office now.”
March 4, 2005
“How’s QCG going?” Sherry asked Jordan at Starbucks on Saturday morning.
Sherry and Jordan hadn’t seen each other since the beginning of the semester when she started to get busy at QCG. Sherry was also a computer science major, and the two met in their computer architecture class during their sophomore year. They were the only two girls in the class, and they worked on their weekly problem sets together.
“It’s good, haven’t worked on the quantum computer yet, though. I’ve been focusing on an algorithms problem, which they’ve let me work on in the lab. You’re taking algorithms now, right? Maybe you’d be interested.”
“Yeah I love that class,” Sherry said. “What are you working on?”
“I’m working on this problem I formulated about finding the optimal path for a mailman to visit all cities with the shortest possible path. I was thinking that Amazon or UPS might be interested in this for optimizing their delivery routes,” Jordan explained.
Sherry laughed. “Haven’t gotten too far on that, I assume.”
“What? I have the algorithm working and just coded it up tonight. It gave the correct solution for the test data and ran pretty quickly.”
“No way,” Sherry said. “You know that problem is NP-complete, right? Ever heard of the Traveling Salesman Problem?”
“I remember learning about NP-completeness in algorithms, too. But I’ve never heard of the Traveling Salesman Problem.”
“Yeah, so you are essentially solving the Traveling Salesman Problem. Given a list of cities and distances between them, TSP returns the route of shortest distance which visits all cities on the list.”
“Whoa, I had no idea,” Jordan said, stunned.
“This is huge, Jordan.”
Jordan knew this was huge. She remembered learning in algorithms class that P was the class of algorithms that could be solved in polynomial time, and NP was the class of problems that could be verified (but not necessarily solved) in polynomial time. For years everyone has been trying to prove that P and NP are not the same. That is to say that not all problems that can be verified in polynomial time can also be solved in polynomial time.
If P and NP are distinct, then no NP-complete problems can be solved in polynomial time. If one of these NP-complete problems is shown to have a polynomial time solution, then all of these problems can be solved in polynomial time and then P = NP.
“What do I do with this?” Jordan asked Sherry.
“Did Dr. Peterson or anyone else at QCG work on this with you?”
“No, they’ve been working on the quantum computer.”
“You should publish it. If you publish your polynomial time algorithm for TSP, then you’ll be proving that P ≠ NP and will win the $1,000,000 prize from the Clay Institute of Mathematics for solving the P vs. NP problem. This is the biggest open problem right now in computer science and math. Solving this will make your career.”
March 3, 2005
Quantum Computing Group
Mike’s jaw dropped when Rick showed him how fast Jordan’s code ran on the 5,000 cities in the dataset.
“I’m going to delete this from Jordan’s computer and have her start working on something else Monday. We need to get rid of this and make sure that no one sees it,” Rick said to Mike.
“Hold on. I’m not sure that’s the best idea. How much longer does our NSF funding last?” Mike asked.
“How much more time do you think it will take for us to finish this quantum computer?”
“Probably eight. We haven’t been making much progress recently, even with the best engineers on the team.”
“Right. Our funding is going to run out soon, and we haven’t gotten very far since you invented the qubit. I have an idea about how we can start making money now. It might be risky, but the reward is unlimited.”
December 3, 1972
University of Mississippi
“Can I buy you a drink?” Rick asked in a deep voice to the blonde girl sitting next to him at Proud Larry’s bar in Oxford, Mississippi.
“No thanks, I don’t drink. I’m just trying to grab a quick bite to eat before I go back to studying” Pam said to Rick, the attractive guy sitting to her left. She never got this kind of attention at bars, let alone to someone this hot. Why would he want to talk to me? “I’ll be right back.”
Rick quickly slipped a pill into Pam’s drink and smiled as he watched the white powder spread through the glass.
“Work… I have to work,” Pam mumbled as she grabbed Rick’s arm. Rick was holding her up; she could barely walk.
“We’re almost home,” Rick said.
“The bit… my paper… publish… make money. It’s big,” Pam said.
On his way out in the morning, Rick saw the paper sitting on Pam’s desk. “Revolutionizing the Bit: Encoding the Superposition of States,” Rick read from the front page.
He grabbed the paper and left. Pam wouldn’t even remember meeting him.
March 3, 2005
Quantum Computing Group
“With TSP solved, we can easily transform the output from that algorithm into the solution for integer factorization, which as you know can be used for decryption,” Mike continued. “HTTPS and SSL are built on encryption algorithms that depend on integer factorization being unbreakable by classical computers.”
“And if we can break HTTPS and SSL, then we can break into people’s online bank accounts,” Rick filled in.
“Exactly. We do need to get the rest of the team on board to help with engineering,” Mike said.
“But how can we convince them to agree to steal money?” Rick asked.
March 4, 2005
Jordan checked her email anxiously for the rest of the day. Earlier she had emailed a few professors, telling them that she proved P ≠ NP by solving TSP.
Everyone knows that P ≠ NP. There must be a bug in your proof.
I’d suggest you continue your quantum computing work at QCG. TSP is unsolvable.
I admire your persistence in tackling such an important problem. But you should shift your focus to proving P ≠ NP instead.
Jordan knew that this was controversial, but she thought that teachers would at least be willing to hear her out. But she knew how important this work was, and already had the algorithm written and tested. Writing up a paper wouldn’t be much additional work, so she decided to go ahead and submit the paper to conferences with deadlines in the coming months.
March 4, 2005
Quantum Computing Group
“Thanks guys for coming,” Rick told the eight engineers in front of him, who had rushed into the office.
“Jordan finished the Traveling Salesman Problem last night,” Rick began, using the information that Mike had just explained to him. “As we know, this means that P = NP.
“This opens up a ton of problems that were previously thought to be impossible in computer science. I think that the most important one for us to tackle is protein structure prediction, which is also one of the most important problems in computational biology. This problem is known to be NP-complete, but given that we can efficiently solve the Traveling Salesman Problem, we can also solve protein structure prediction.
“There are thousands of strains for influenza each year, and there is currently no robust way to predict what the next strains will look like. This means that drugs can’t be designed to protect these viruses before they actually start affecting people. If we can predict the structure of proteins, then we can foresee diseases before they happen and provide better preventative treatment,” Rick explained.
“Wow, this is amazing,” said Albert, one of the new engineers.
“We could save a lot of lives with this project,” Mike said.
“How will we get the money to do this research?” asked Sam. “Our grant won’t cover it.”
“Right, here’s where it gets tricky,” Rick said. “Another NP-complete problem that we can now solve is decryption. TSP is a harder problem than decryption, and we can transform the output of TSP into the correct solution for integer factorization, which will break many forms of encryption.”
“HTTPS and SSL, which ensure security across the Internet, depends on the theory that encryption cannot be broken by using classical computers,” Mike chimed in. “Consider the basic example of logging into Facebook. When you enter in your credentials, your username and password are sent over the Internet to Facebook. If someone tried to intercept this communication, they would fail to retrieve the information because the connection is secure. Using standard methods today, they wouldn’t be able to decrypt the connection.”
“So we can use our new decryption algorithm to intercept Facebook passwords,” Sam extrapolated. “But why would we want to do that?”
“Facebook is just one site running on HTTPS and SSL,” Rick explained. “All websites which use confidential information like passwords are using these technologies. This includes online bank portals. We can intercept the connection between users and their bank accounts. From there, we can transfer money into our accounts to fund the protein research.”
“Doesn’t sound like it would be too hard if we have the decryption algorithm” Sam asked. “But do we want to be hacking into people’s bank accounts?”
“Out of context it might seem unethical, but we have to think about the tradeoffs,” Rick said. “We can save millions of people’s lives with protein structure prediction and preventative medicine for life-threatening diseases. We could earn billions from that, maybe even pay the people back in the future, whose money we are taking now. This would also obviously be incredible for all of our careers.”
“What if Jordan publishes her TSP algorithm?” Albert asked. “Then everyone will start working on this.”
“Yeah, we need to start right away,” Rick said. “I’ll take care of Jordan.”
March 5, 2005
Still checking her email for professors’ responses, Jordan found an email from Rick.
Thanks so much for your hard work these past few weeks. The mailman problem was a fun problem, and it was great to watch you see it from start to finish. However, we’ve decided to shift our full focus to quantum computing. Unfortunately, since you don’t have much experience directly with quantum computing, we’re going to have to let you go.
I know you want to go to graduate school, and I’d be happy to write you recommendations anywhere.
We’ve cleared your desk and given your laptop and desktop computers back to the school, so no need to come by the office.
Shit, Jordan thought. She’d have to write her TSP algorithm over from scratch, and now QCG wouldn’t be able to help her with a paper.
June 10, 2005
Subject: [SIAM-05] Your Paper #568
Dear Jordan Harris,
We regret to inform you that your paper #568 with title: “A Polynomial-Time Solution to the Traveling Salesman Problem” has not been accepted for publication in the Society for Industrial and Applied Mathematics Journal on Computing.
The review process was extremely selective this year. Thank you for your submission, and we encourage you to submit again next year.
SIAM-Computing 2005 Program Chairs
This was the sixth rejection email so far for Jordan’s paper about TSP. She knew that her paper was controversial, since everyone believes that P ≠ NP. Without the support of QCG or faculty advisors, she wouldn’t be able to publish this as an independent college student.
June 11, 2005
Quantum Computing Group
“Hi Mona, can I please talk to Rick?” Jordan asked Mona at the front desk.
“I’m sorry, I can’t allow you past this door. Would you like me to pass him a message?” Mona said.
“Send her through, Mona,” Rick called from the office.
“What did you want to talk to me about?” Rick asked Jordan as he sit in his office with his legs up on the desk.
“The Traveling Salesman Problem,” Jordan began. “Solving it means that P = NP! This is huge. We don’t need quantum computers for decryption, we’ll be able to solve this efficiently. There are so many more problems, too.”
Rick looked at Jordan, so excited about her findings. He could tell her she was crazy, just like anyone else would. He knew the code worked; he saw how fast it ran. But she had no chance winning the Clay Prize or getting this accepted for publication.
“I really want to publish the result,” Jordan continued. “We’ll win the Clay Prize and can put the money towards QCG.”
“Have you told anyone about this, Jordan?” Rick asked.
“I emailed a few professors and tried to submit the paper, but it hasn’t been accepted anywhere. Here’s the paper,” Jordan said, handing it to Rick.
“Thanks Jordan,” Rick said. “I’ll take a look.”
At least she’s agreeable, Rick thought, thinking about when he stole the qubit paper from Pam.
January 15, 2006
Massachusetts Institute of Technology
With her last graduate application submitted, Jordan felt free and ready to finally enjoy her senior year without stress. Rick’s recommendation letter would get her into any grad school she wanted. She thought that with the right computer science advisor in graduate school, she’d be able to work on the proof and get it published finally.
Over the last semester, she watched the news about QCG adding a new biomedical research branch chartered to work on protein structure prediction. She wasn’t sure how that was relevant to quantum computing, but she didn’t know much about biology anyway, and this new project didn’t interest her very much.
On her way to her first physics class of the semester, Jordan picked up a copy of MIT’s student newspaper “The Tech”, and saw the following article on the front page:
QUANTUM COMPUTING GROUP SNAGS $1,000,000 FOR SOLVING P = NP
QCG has reportedly proved that P = NP, a groundbreaking discovery in computer science and mathematics, via an efficient algorithm for the classic Traveling Salesman Problem. With the proof, the group gets a $1,000,000 prize from the Clay Institute of Mathematics, who posted the reward with the original call for a solution. The group is led by Dr. Richard Peterson, acclaimed researcher and inventor of the qubit.
“I’m really proud of the group for all their hard work in proving P = NP,” Dr. Peterson said. “We are proud to put this money towards a new project on protein structure prediction, which will help us design drugs which preemptively prevent diseases such as influenza, polio, and Hepatitis.”
Jordan rolled up the newspaper and slid it into her backpack. The professors didn’t believe her when she claimed to have a proof for P = NP, and they certainly wouldn’t believe her that QCG stole the idea from her.
Dr. Peterson was now not just a celebrity in computing—he was a hero in medicine.
September 24, 2006
California Institute of Technology
Finally settled into her classes in her graduate program at Caltech, she organized a meeting with one of the professors working at the university’s Institute for Quantum Information.
“Now tell me, Jordan, what did you work on at QCG?” Dr. Gold asked.
Jordan described the mailman problem and her polynomial time solution.
“The Traveling Salesman Problem—that’s how QCG proved that P = NP. I didn’t see your name on the paper,” Dr. Gold said.
Jordan shook her head.
Dr. Gold sighed. “Rick, he stole the paper from you, didn’t he?”
“Do you know him, Dr. Gold?” Jordan asked.
“Call me Pam,” Dr. Gold said. “Let me tell you a story about how I met Rick.”