Monday, December 31, 2018

Book review: Jo Walton "Just City"

This was an easy and pleasant read. But it could have been so much better if it had actually tackled the premise that it promised. The premise seemed ambitious; ir promised speculative fiction with the capital S. But it didn't deliver.

The Just City in the title of the book is the city that Plato talked about in the Republic. The story describes the social experiment of the Republic implemented in real life. It's set on an island somewhere, presumably, in the Mediterranean sea, in an undefined time in the prehistory. The time it's set in is before the rise of the classical world. Even Illiad and Odyssey had not yet been written. It doesn't matter, because the inhabitants of the island are completely shut off from the surrounding world and have no interaction with it. Most of the inhabitants are 10-year-old children (10080 of them), that were bought from slave traders of different eras, and brought to this island, across time, to be raised according to the Platonic concepts of justice. They are expected to implement Plato's Just City in real life. They are schooled by a number of teachers from different eras of history, and all of them have one thing in common is that at some point they prayed to Athene. For it was Athene that set up this experiment, and transported people through time to bring them here.

The plot of the book is rather uneventful, but I was hoping for plot twists based on the moral dilemmas these people face, and how they have to adjust their experiment when it is not turning out as planned. Of course, the experiment does not turn out as Plato envisioned, because people are people and they bring their human natures with them here. They also bring their prejudices, perceptions, beliefs, and ways of doing things from their eras. So, not surprisingly, even in the Just City rape victims are still responsible for their rape.

What's odd is that the "masters" -- the teachers who are responsible for the upbringing of these 10080 children -- do not question the notion of justice beyond the Platonic ideal. This ideal was held by a person who lived 2000+ years ago, and much of it doesn't jibe with our modern notion of justice. And many of the masters were from eras historically close to ours, or even beyond ours.

So it's strange that none of the teachers entertain a more modern paradigm of justice, even in the matters of life and death. Such as availability of modern medicine. Athene "imported" something from technologically advanced era (I won't say what, because one of the plot developments hinges on that), so she could have imported advanced medicine as well. And yet they don't treat sick newborns, but "expose" them, i.e. leave them in the wilderness to die. They oddly think it's more humane than to kill them. They do it even to the babies with small birth defects like cleft lip or palate, which are entirely correctable in our times. What about treatment of injuries and illnesses that surely must have occurred among those 10080 children, because of sheer statistical likelihood? Was their medicine as barbaric as the medicine of the ancient times? To be fair, one of the teachers mentions "mold drugs", so apparently they did import the antibiotics from the future. But what about everything else? I would think that realistically this question would have popped up very early in the existence of the city, and I also think that those teachers who came from the more modern times would find it a gross violation of ethics to not provide lifesaving treatments when they could be brought in from the future. And if you are dedicating your whole life to put a vision of justice in reality, then surely you would assign the utmost importance to ethical questions?

In other words, I expect that realistically in such a city there would be never ending debates, serious arguments, maybe even fights over whose ethical system is considered the most just. Yet none of it happens. Everybody leads largely untroubled existences filled with philosophy, music, arts and sports, and nobody runs into ethically ambiguous situations, in which Plato's vision directly contradicts their own internal sense of justice.

To be fair, something similar does start to happen towards the end, but it was a bit too late to make me "buy" into the book. The whole book seemed like one big missed opportunity to get deeply into ambiguities and paradoxes of justice.

Tuesday, December 25, 2018

Natural Language Processing hackathon, or don't judge the wine by the shape of the bottle

In April of 2018 I went to a Natural Language Processing hackathon. Organized by Women in Data Science Austin, it took place at Dell, where one of the organizers worked. This was not the kind of hackathon where you hack for the whole weekend straight, crashing on a beanbag to catch a few winks in the breakroom of some hipster startup. No, this was a hackathon with work-life balance. It lasted from 10 am to 3 pm on a Saturday, which is just enough time for you to get deeply enough immersed in a subject to fire up your appetite for it, but not get sick of it. There were no minimal viable products produced, and no prizes, but I got to sink my teeth into the basics of Natural Language Processing.

A data scientist named Becky, who does Natural Language Processing for an Austin company, introduced us to the three cornerstone approaches of NLP -- summarization, topic modeling, and sentiment analysis.

Data scientist Becky talks about topic modeling
Data scientist Becky talks about topic modeling.

Sentiment analysis quantifies the subjective emotion in a text, e. g. did the majority of reviewers like or didn't like a particular wine? Data scientists don't take into account just the words, but also such nonverbal information as capitalization (a word in all caps is likely to mean the author feels strongly about it), and emoji. Topic modeling finds abstract concepts that occur in a body of texts, a. k. a. corpus. For exaple, if it finds the words milk, meow, and kitten, it might decide one of the topic of this text is cat. If it finds the words bone, bark, and puppy, it might decide one of the topics is dog.

Summarization reduces a text to several key phrases or a representative sentence. Summarization can be extractive or abstractive. Extractive summarization selects a few representative sentences from the text, while abstractive summarization creates a summary of the text.

As an example, Becky gave a phrase: "The Army Corps of Engineers, rushing to meet President Bush's promise to protect New Orleans by the start of the 2006 hurricane season, installed defective flood-control pumps last year despite warnings from its own expert that the equipment would fail during the storm, according to documents obtained by the Associated Press."

Extractive summarization would extract such phrases from it as:

  • Army Corps of Engineers
  • President Bush
  • New Orleans
  • defective flood-control pumps

In contrast, abstractive summarization would generate such phrases as:

  • government agency
  • presidential orders
  • defective equipment
  • storm preparation
  • hurricane Katrina
Natural Language Processing hackathon hosted by Women in Data Science Austin
As many of the hackathon attendees as could fit in the picture.

I can't quite put my finger on it, but it seems that extractive summarization extracts names of specific entities, but not much information as to what happened to those entities or what did they do. But abstractive summarization seems to "understand" what those entities actually represent and what they do, and thereby extracts more "gist" from the paragraph. I could be wrong about it, of course.

According to Becky, extractive summarization is a mostly solved problem by now. TextRank algorithm takes care of it. But abstractive summarization is a very difficult, unsolved problem, though knowledge graphs help.

At the organizers' suggestion, the attendees arranged themselves into three teams, each focusing on one of those three pillars. The organizers brought with them the corpora, a. k. a. texts to be analyzed. Specifically, they brought wine reviews, lots and lots of them. I suppose that's the second best to bringing the actual wine.

Summarizing wine reviews means extracting an "essence" of what the bulk of the reviewers said about a particular wine. It means identifying certain qualities that most reviewers noticed in a given wine. Sentiment analysis meant identifying whether the reviewers thought mostly positively or mostly negatively about the wine.

I ended up in the summarization team. Lead by Randi, who is a data scientist at a big company, we analyzed the wine reviews. By that I mean we called a bunch of functions from pandas, textacy, sumy and other relevant Python packages. The results were mixed. For example, sumy summarized reviews of Moscato in two sentences, but we had no way to tell whether this summarization is good, i.e. whether those were the most representatives sentences from the reviews. It's funny how this is the kind of problem that one has no way of verifying -- at least none that I learned in my 5 hours of NLP bootcamp. Sure, you could read hundreds of reviews and try to get a "feel" whether those sentences were the most representative, but your "feel" would be subjective.

It makes Natural Language Processing feel like black box, and almost like magic -- until you notice that when you ask for 5-sentence summary, the summary includes duplicates for first two sentences. That looks odd, so you take a closer look at the texts and notice that there are duplicate sentences in the document itself. For all its magic, sumy can't figure that out.

Within sumy, you can choose which summarizer to use. First we used LexRank, and it turned out to be very slow. Then we tried another, LuhnSummarizer, and it was much faster, but the results not nearly as accurate. But how would you decide how accurate a summarization is, given that there are no exact criteria for accuracy that I know of? Well, the first summary described mouthfeel and acidity of Moscato. The second included things like the shape and color of the bottle. It left me with the same feeling one often gets interacting with artificial intelligence, that it's both very smart and very stupid at the same time.

Tuesday, March 20, 2018

Introduction to Natural Language Processing with Women Who Code

In 2016 Women Who Code Austin hosted a series of five presentations on Natural Language Processing. The presenter was our member Diana, who has a Ph.D. in linguistics and has worked in the area of computational linguistics for many years. She did demos of some basic text analysis one can do with the Python Natural Language Toolkit, or in short, NLTK.

She presented all this as a Python notebook. A Python notebook is software that lets you combine text, code, and output of that code on one page. You can run a code snippet right there in the notebook, and the resuls will get updated automatically. So equipped, Diana introduced us to the basics of what computational linguists do. Or if that sounds too ambitious, let's just say she showed some simple things one can do with NLTK.

For example:

  • read in the text,
  • tokenize,
  • tag,
  • remove punctuation,
  • remove stopwords...
  • build a frequency hash table from the rest of words.
The first Austin Women Who Code meeting on natural language processing, with our instructor Diana standing in the center
The first Austin Women Who Code meeting on natural language processing, with our instructor Diana standing in the center

She introduced such concepts as collocations and bigrams. Bigrams are pairs of words that are next to each other in a text. Collocations are pairs of words that naturally occur in the language together, i. e., a chance of them occuring together is greater than random. An example of a bigram that's not a collocation is Trump's usage of a phrase "Liar Ted" (this was the spring of 2016, the height of the Republican strife for a presidential nomination). If a bigram is not a collocation, but occurs more often than randomly in a text, that can help to identify who the author is / who the speaker is, and some such qualities. It can be a fingerpint of sorts.

The aforementioned tagging is something we do after tokenizing (roughly speakinng, breaking the text up into words). Tagging assigns a 2-letter tag to each word, marking it as a part of speech, such as noun, adverb, etc. "You can use a big list of tags, or a simplified one. Using a simplified list of tags can help with speed of analysis of your corpus," said Diana.

Here Diana noted that tagging words as parts of speech has inherent ambiguity in it -- exactly the kind of thing that makes language and its computational processing so interesting. Here is an example of parts-of-speech ambiguity in a sentence: "They refuse to permit us to obtain the refuse permit". Still, the Python Natural Language Processing Toolkit correctly tags the first "refuse" and "permit" as verb (VBP) and the second instance of each as noun (NN).

NLTK correctly identifies parts of speech in the sentence 'They refuse to permit us to obtain the refuse permit'
This slide shows how NLTK correctly identifies parts of speech in the sentence above. The first instances of "permit" and "refuse" are "VB" -- verbs, whereas the second ones are "NN" -- nouns.

At the second meeting we did all those actions with a corpus of -- wait for it -- Hillary Clinton's emails. Her emails were available for download from the Kaggle site. This was still the spring of 2016, and we did not yet know how sad the implications of those emails will turn out to be, so the choice of the subject wasn't as... emotionally loaded as it would have been just half a year later. And to say "we" did this is an exaggeration, because it was actually Diana that did all the processing and presented the code and the results to us in a Python notebook.

Here was the complete agenda of the meeting:

  • Getting data: Hillary Clinton's emails;
  • Reading files;
  • Using Pandas to create a Dataframe in Python;
  • Cleaning data: eliminating punctuation, eliminating stopwords, normalizing data: converting to lower case, tokenizing words
  • Visualizing data.

All of this pre-processing of data was done in the Python Natural Language Processing Toolkit (NLTK).

I must say I would have preferred it if Diana had set up this mini-course as a series of exercises for us to do in class and write some code calling NLTK methods ourselves. But if we had done that, we would not have been able to cover even half as much in those four meetups. So I appreciate what Diana did. At least she showed us what kind of beast NLTK is and which fork to eat it with. In the process learned some basic NLP lingo, such as:

  • corpus -- a body of text, plural corpora; it's what you process to extract words and do computations with them;
  • lexicon -- words and their meanings; example: English dictionary.
  • However, you need to consider that different fields will have different lexicons. For example: to a financial investor, the first meaning of the word "bull" is someone who is confident about the market, as compared with the common English lexicon, where the first meaning of the word "bull" is an animal. As such, there is a special lexicon for the financial investors, doctors, mechanics, and so on.

  • token -- each "entity" that is a part of whatever was split up based on rules. For example, each word is a token when a sentence is "tokenized" into words. Each sentence can also be a token, if you tokenized the sentences out of a paragraph.
  • frequency distribution. The frequency distribution method of NLTK counts the frequency of each vocabulary item in the text. It helps identify the most informative words in a corpus.

So overall I got a little familiar with what are the very basics of what natural language scientists do. But somehow, during those four meetings I was still hoping that we'll get past collecting the statistics about words, and get to some mysterious insights about how language works, evolves, and transforms our thoughts, that only computer analysis of language can provide. Of course, my expectations were unrealistically inflated for a set of introductory lessons.

Going back to Hillary Clinton's emails, here is how you would analyze them. This is an "Exploratory Analysis: Getting and Cleaning Data" slide. Here you see the metadata fields that were extracted from the emails. There are quite a few of them.

Python dataframe with the metadata fields extracted from Hilary Clinton's emails
Python dataframe with the metadata fields extracted from Hilary Clinton's emails. Python dataframe with the metadata extracted from Hilary Clinton's emails
This slide, "Slicing dataframe to extract subject", shows Python method calls that you would use to extract the email subjects from the dataframe shown in the previous image. Presented in a Python notebook, it alternates code with results of that code. The results can be updated on the fly if you make changes to the code. The MetaDataSubject and MetaDataTo fields contain some familiar names and topics that made the news...

The next slide shows the use of the NLTK method "concordance". It produces a list of the words used in the text, with the passages where they are used. So if you want all occurrences of the word "surprise" in Jane Austen's "Emma", with snippets of context, you can call


(Here, emmaText is the variable that holds the text of the Jane Austen's novel "Emma".) From this example you can also see that NLTK has corpora of texts from the Gutenberg project, which is pretty handy.

Concordamce: all the places in Jane Austen 'Emma' where the word 'surprize' is used
Concordamce: all the places in Jane Austen 'Emma' where the word 'surprize' is used, obtained by calling a 'concordance' method of NLTK.

Venturing ddeper into natural language processing

The easiest texts to analyze are the news, Diana said. News have very good structure. Sentences tend to be short, and tend to have classical structure: subject, verb, object, etc. Medication instructions are also easy to analyze, since they are required to have readability scores high enough to be suitable for 9-12 year olds. But in literature the sentences are often not conventional and much harder to parse.

At the last meetup we talked a little bit about analyzing texts "for real". And by that I mean a little deeper analysis than just breaking up sentences into parts of speech and gathering statistics about it.

One example where computational linguistics is used is to grade student essays. If you have so many essays that hiring human graders would be cost-prohibitive, natural language processing can help. For example, if an essay is supposed to be on the US Declaration of Independence, the script would check to see if certain words are present in it in a certain way, and will conclude that that student might have a certain level understanding of the topic. (Yes, I know, this raises lots of questions about creativity versus cliche'd, cookie-cutter texts: the latter would be more likely to hit all the points that a grading program is looking for, whereas the former might be difficult for a program to discern. But we didn't cover such questions at the meeting, since it's an uncharted territory.)

We touched upon sentiment analysis, which helps determine how customers feel about an experience they had with a brand or a company. Companies like HomeAway use it to analyze customer reviews of their rental properties. And they discover unexpected things that way. For example, analysis of customer reviews of B&B-type places showed that the greatest predictor of customer satisfaction is whether a house has pots and pans.

Sentiment analysis also shows that, for example, if you try to infer customer satisfaction from the reviews by searching for wait times, you'll get inconsistent results. 15 minutes would be bad for a restaurant, but lightning-fast for an emergency room.

And this is where people try to determine degrees and ways of relatedness or similarity between concepts.

For that, they can use ontologies.

What is Ontology?

A consensus is now established about the definition and the role of an ontology in konwledge engineering: "An ontology is a formal, explicit, specification of a shared conceptualization".

It is used in cognitive modeling.

More about Ontologies

An ontology is a schema (model) describing the types (and possibly some individuals) in a domain, the relationships that may exist between types and individuals, and constraints on the way individuals and properties may be combined.

Here are some examples of ontologies

  • Classes: Project, Person, ProjectManager. ProjectManager is a subclass of Person. People and Projects are disjoint.
  • Relationships: worksOn, manages. Manages is a sub-property of worksOn.
  • Constraints: People work on Projects, not the other way around. Only ProjectManagers can manage Projects.

This simple example enables machine inferences, e.g. if X manages Y, then we can infer that Y is Project, and X is a ProjectManager and therefore a Person.

Onthologies allow people to create trees representing relationships between concepts, like this:

A tree that expresses relationships between conecpts in the academia (Student, Employee, Faculty, etc)
This is an example of a tree that expresses relationships between conecpts in the academia (Student, Employee, Faculty, etc.)

Some people propose ways to neasure the similarity of concepts by some graph metrics, such as the shortest path between two nodes.

Measure of similarity between two concepts in a graph, expressed in terms of a shortest path between two concepts.
Measure of similarity between two concepts in a graph, expressed in terms of a shortest path between two concepts.

More pictures from the Women Who Code Austin meetup series on Natural Language Processing are in my photo gallery.

Tuesday, February 20, 2018

Margaret Atwood at the Texas Book Festival in 2015

Margaret Atwood was interviewed at the Texas Book Festival in October of 2015. I have only read one of her books, The Handmaid's Tale, and as we know, it's a depressing and scary book. Considering that, the interview was surprisingly (to me) light-hearted and revolvedheavily around popculture. I got an impression that Margaret Atwood is quite engaged with it. She participates in art / experimental projects that revolve around books and reading.

One of such projects was the Future Library in Oslo. It was started by an artist Katie Patterson. In May of 2014 she planted 1000 trees near a forest in Oslo. These trees will grow for a 100 years. Every year a different writer from around the world, invited by a committee, each writing in a different language and different genre, will contribute a manuscript in a sealed box to the future library. 100 years later all the boxes will opened. There will be enough wood from the trees that have grown to make paper to print the anthology of those stories.

As Margaret Atwood explained, the stories can be in any form: one word, a poem, a short story. No images. And you cannot tell anybody what is in the box, except for the title. But these boxes will be in the future library with the author's name and title visible. You can go into the library, see the names and titles and imagine what could be in them. "So in May (of 2016), I'm going to Norway with my box, tied with a nice blue ribbon," said Margaret Atwood. "I imagine there might be a moment at the immigration checkpoint where they're going to ask me what is in that box, and I'm going to have to tell them, I don't know," she said, adding that that might not go over well.

She also noted that the success of this project was based on a number of assumptions: that people will want to read and will be able to read, that Oslo will still be there. (Not to mention an even more questionable assumption that books in a hundred years will still be printed on paper -- E.)

Margaret Atwood seems to encourage all the ways in which people consume and produce the written word nowadays, including mashups and remakes. For example, she wrote her own version of Shakespeare's play "Tempest" for the Hogarth Shakespeare project, in which modern writers reimagined Shakespeare's works. She had a fan fiction contest for her latest book. (And no, she replied, she wasn't going to read all the thousands of entries herself. She had slush readers for that.) When asked if she was ready for other people to take over her characters, she indicated she had no problem with that. She said: "Fanfiction is very very old, except it wasn't called fanfiction. It started with the Greek mythology. When Don Quixote was published, there were a lot of other books published about Don Quixote by other authors. So Cervantes had to put out a notice that those other books aren't authentic."

She also contributed, even if in a small way, to the Zombies, Run! app. It's an interactive app for exercise, based on the premise that a zombie apocalypse is taking place, and you are running from the zombies. At one point the run takes you to Canada, but the entire Canadian government has been zombified, and the entire NHL hockey league are zombies on skates. However, you can establish contact with Margaret Atwood. Naomi Alderman, co-creator of the Zombies, Run! app, wrote her into the game. The way Margaret Atwood explained it, "I'm a pushover. You want to put me in a zombie game? Okay."

Margaret Atwood at the Texas Book Festival in October of 2015, surrounded by the audience members
Margaret Atwood (left) at the Texas Book Festival in October of 2015, surrounded by the audience members.

Despite the lighthearted tone of the conversation, the interviewer couldn't help but note that we were at the Texas Capitol, the place where Texas Legislature makes laws -- and some or many laws that they passed recently resonated strongly with the themes in Margaret Atwood's most famous dystopian novel "Handmaid's Tale". You could get an impression that Texas Legislature used "Handmaid's Tale", um, aspirationally. So, not surprisingly, the interviewer brought up political topics.

"Margaret, you do a lot of advocacy work. And we are in the Texas state capitol, so I want to ask you about how far we have come and how far we have to go," said the interviewer, Kelly. (I don't remember her last name -- E.)

Margaret Atwood quipped something about making a law from here. (The interview took place literally in the House Chamber of the Texas Legislature. All the audience were sitting at the lawmakers' desks.) Then she said:

"The people who passed it (referring, I think, to a recent law severely restricting availability of abortion -- E.) don't think about the effect there will be down the line. Real people will have to live with these things. The effects will turn out to be not what they thought to be. For example, California reversed its draconian prison legislation because they couldn't afford it. I don't think you can really sustain the society if you alienate a lot of young people, because they're going to move somewhere else, and then who's going to pay for your old age? If you are prohibiting abortions, you may think that there will be lots of babies born, lots of poof children, future serfs? That might not work out that way."

As usual, there was time for audience questions.

A question from the audience. Oslo is building huge library, but a few hundred feet from here there is a huge library that's mostly empty, there's nobody there. (I think he might have been referring to the Austin Public Library central location. -- E.) So why do you think that the Oslo Future Library be successful?

Margaret Atwood replied that some libraries were very heavily used, for example, the New York or Toronto public library systems. "So I don't think it's a question of library or no library, it's a question of what kind of library, how accessible it is, and what kind of interactivity do they do? I believe that access to books and reading is one of the cornerstones of the democracy," she said.

A woman from the audience says she's getting her PhD in literature, and (if I understood correctly) is teaching literature to freshmen. Making them read feels like she's murdering them. She asks if Margaret Atwood sees it a general rule of thumb for this generation (unwillingness to read), and if so, does she have any advice?

Margaret Atwood. Freshmen read all the time. You can't use internet without being able to read. There is a place where they can write anonymously, and post what they're really interested in, which may be vampire stories. Another way you can help them is audiobooks. But sometimes they just want to put in the studying time. When I was teaching grammar to engineering students, I started them on Kafka's parables, which are very short. So you can start your students on flash fiction. They're all 18, it's a difficult age. When I taught the same class to returning students, there was a huge difference. They wanted me to challenge them, they argued with me.

Make your students write a zombie or vampire story. Or an article of economics of vampires. Vampires are always rich. Why is that? They are immortal -- if they became a vampire in 1930, how much money you have accumulated? Have them do a business plan for being a vampire. There are two vampire movies where this accumulation of the riches is done explicitly. 1. An Iranian vampire western movie called "A girl walks home alone at night" - a feminist Iranian vampire, who was killing only bad people, but in the process she accumulated a lot of diamond watches. 2. "Let the right one in", with a 12 year old girl vampire. There is a classic line in it: a little boy says to her when he [starts suspecting something]: 'How old are you really?' She replies: 'I'm really 12. I've been a child for a very long time.'"

A woman from the audience. What words of comfort you have for readers who know they'll never lay their eyes on your contribution to the future library?

Margaret Atwood. There are many books you'll never lay your hands or eyes on, because you've never heard of them. As a tribute to that idea, find a book you never heard of, read it, and find other people who love it.

Friday, December 15, 2017

Arianne "Tex" Thompson's worldbuilding workshop at ArmadilloCon 2016

Subtitled "Escape From Clichea", Arianne "Tex" Thompson's worldbuilding workshop was the most remarkable event at the ArmadilloCon 2016, and was alone worth the price of admission. She gave a heap of good, practical, doable recommendations on how to improve your worldbuilding, storytelling, and characters. At a typical writing workshop you'll get vague advice like "show, don't tell", and "kill your darlings", but rarely will you hear specific recommendations what to do. But Tex Thompson's workshop was an avalanche of such implementable nuggets of goodness. She showed us how to look at your story material differently and tease the interrestingness out of it.

To be sure, this wasn't the kind of workshop where professional writers and editors critique your manuscript. This was 1.5 hours of Tex Thompson speaking. But I came out of it full of ideas of how to make my stories better.

I wrote them down to the extent I remembered them.

The workshop wasn't strictly just about worldbuilding, but also covered deeper aspects of writing, like how to find your identity as a writer, how to find what makes you unique, and use it to build your online presence.

On how to build your identity as a writer

Write down 3 things you have been paid to do. Then 3 things you could write an article about. If the things on those lists have nothing to do with writing, that's completely fine. Those are things that make you unique. They help you stand out between other writers. If nothing else, they could give you ideas for your blog posts, and a blog is a big part of how a writer attracts and keeps an audience.

Here is another way to mine ideas for blog posts.

Write a list of 3 stories that you want your work to be compared to. Then write down common elements between them. For example, Tex Thompson said that for her, those elements are: (1) ensemble cast / team effort; (2) people with different abilities or powers; (3) big, wild, slightly-ruined world. Such elements are great for mining ideas for your blog or convention panel topics. For example, combining (1) and (2) could lead to Top 10 teams in comics.

Other lists to tease out your identity

Things you would you do with your life if you won a million dollars

What you tend to get into arguments about

Worldbuilding exercises

Association exercise. What do the words "four kingdoms" remind you of, asks Tex Thompson.

Audience says: 4 elements, 4 directions, 4 seasons.

Tex Thompson. Take your first idea and place it carefully in the garbage. Because it is also many people's first idea.

What could be a fresher take on the "four kingdoms" idea? The audience replied:

  • Aliens come and the kingdoms have to unite to defeat them;
  • Economics arms race;
  • Each of the 4 lands has a princess and they are all supposed to be in a beauty pageant, but one of them has a prince and he wants to compete too.

Best practices for writers

Arianne 'Tex' Thompson at the Escape from Clichea worldbuilding workshop at ArmadilloCon 2016
"Arianne 'Tex' Thompson leads the Escape from Clichea worldbuilding workshop at ArmadilloCon 2016. More pictures from ArmadilloCon 2016 (39) are in my photo gallery.
  • Use the Triforce!
  • Triforce consists of: Education - something you know about; Passion - something you care about; Inspiration - something you are excited about. At the intersection of those things is a story that only you can write, says "Tex" Thompson.

  • Ask yourself: "what is the easiest, laziest thing I could do here?" Then do something else.
  • Start with Episode IV, and leave space for more stories as you go.
  • What happened in Harry Potter world before the HP started? All the Voldemort stuff, the Marauders. Your idea for the front story might make an awesome back story.

  • Question your assumptions.
  • Have you read a story about space travel that's set in the 25th century, but all the gender norms are from the 20th century? Or they have all the same notions of nuclear family and property?

    Everything that surprises you about another country / culture says something about your own. There is a book series CultureShock! that explains how to live in another country. In US it says, don't drop off at someone's house uninvited. It's OK to ask what people do, but not how old they are. You can call uninvited, but not after 9 pm. Never cut in line, that will not be good to you.

  • Give us something we expect and something we don't.
  • Many enormously successful TV and book series do that. Star Trek: a Western but in space. Game of Thrones: medieval fantasy, but gritty / realistic. Harry Potter: witches / wizards, but in high school. Another example. Chuck Wendig once asked: what would a vampire do in a zombie apocalypse? In "Double Dead", the vampire tries to make sure that the human race does not go extinct, because then he'll be out of food. So he herds human survivors through the apocalypse.

    In any scenario, ask:

    • Who benefits from the current state of affairs? Who tends to benefit in most zombie apocalypse stories? Zombies, warlords, gritty surrivors. Even in the worst of times somebody turns a profit. Doomsday preparers, escaping prisoners, drug companies? Gun manufacturer Colt?
    • Who loses out? Who is the first to go? The slow and the sick. The people on the front lines where the apocalypse started -- hospital workers who got blood sprayed on them. They are gone.
    • Who's trying to maintain the status quo? Usually people who are winning, or people who think they are getting a better deal than they would otherwise. How many of you stayed in a crappy job because its certainty was better than the uncertainty of the alternative?
    • Who is trying to change things? Someone who is losing, who has nothing left to lose.

Explore the timeline

While my memory of the workshop is already vague, I think this was a segue of the "vampires protect people from zombies" exercise. I assume this all means not that we, writers, need to explore all these time periods in our prose, it's just that perhaps the story could be built around not the event itself, but what happened n number of years later.

  • 3 months later: chaos, social collapse, ragtag survivors
  • 10 years later: status quo; the world is relatively stable. But what are we doing now that we weren't doing 3 months after the event? Maybe we are enslaving zombies. We have started to adapt to this new world.
  • 50 years later: the idea that there was something before this seems strange. You still have people who remember the old world, Kennedy's assasination, the days when presidents used to drive down the street in open convertibles. But also the current generation may not know or appreciate reasons for the current state of affairs. This leads to a possibility of a new conflict. They have no respoect for their vampires-elders. They don't understand why people submit to the vampire lords.
  • 100 years later: nobody remembers the way it was. Nobody alive today remembers the flu pandemic of 1918. From the 50s to the 90s our big preoccupation was the cold war and the Bomb. Now everybody has a bomb. We don't worry about Russians launching nukes so much. We are worried about people sitting next to us in a movie theatter. The Great War doesn't come up so much as it does in the fantasy novel prologues.

How much info to dump?

When Tex Thompson teaches at the DFW writers workshop, she tells writers: don't pack me a lunch, leave me breadcrumbs. If your mom packs you a lunch, you'll throw away the apple, trade the cookies, etc. You are more like T-Rex: you don't want to be fed, you want to hunt.

Give readers just enough information about your world to build something of their own

Consider how many bigger-than-big franchises -- Harry Potter, Star Wars, Marvel Universe, Lord of the Rings, Game of Thrones, Pokemon -- give you enough information so that you can create your own Jedi, superhero, wizard school, etc. And they make the world vast and intriguing enough that you would WANT to! Ask yourself: what am I giving my readers to do while they wait for my next book? Fan theories about what is Jon Snow's real heritage, Rey's from Star Wars real heritage, etc. Can they make a costume of a character? In how many ways can they participate in this world? In what ways can you make it exciting to participate?

Tex Thompson enjoyed Harry Potter, but like many fantasy novels, the main character was a dude. She wanted to make her own hero. For example, in the world of Sugar Rush racers, who are all named after candy, Tex's friend made his own Sugar Rush racer, Molten Milk Toast. Does your world accommodate other heroes? Do you establish your world well enough for your fans to actively participate in it? And is it interesting enough that they would want to? If your wizard school is in UK, would the readers wonder what it would be like in the Caribbean?

A guy in the audience. Leave the rules a little open, that the people would wonder how much is possible.

Tex. Right. We need some rules at the outset, but we don't need them all right away. And a lot of the secret sauce is what is the right order of revelations so that they would let people build upon one another, etc.

Use the Triforce, Luke

"Use the Triforce, Luke! Triforce consists of Passion, Education, or Inspiration -- in other words, something you care about, something you know about, and something you are excited about. At the intersection of these three lies a story only you can write. More pictures from ArmadilloCon 2016 (39) are in my photo gallery.

Problem: infodumps are boring

Solution: do not let your story answer any questions the reader hasn't had time to ask!

Give out world details and exposition like treats. Instead of infodumping an explanation of how the star drive work, ask yourself, what question is that an answer to? The question probably comes up when the star drive is broken and needs to be fixed. "We need a new flux capacitor, or else the discombobulator won't work."

What excuse do they make for explaining magic in Avatar the Last Airbender? "Why is so-and-so special? Why can he control all 4 elements?"

Anything you are tempted to go on and one for 100 pages about, make it the focal point of your story. Make your story about how to survive on Mars, and hundreds of pages on growing potatoes will become relevant.

Problem: making a fictional world as detailed as the real wone would take forever, and also be super boring. What should you do?

Answer from the audience. Use the same cliches as in the real world?

Tex. Yes. Use the words "magic wand". Readers already know how it works. Or "hyperdrive". Everybody knows what it is.

You don't want to include things that are not relevant, things that have no emotion attached to it. But if I tell you what magic the blue crystal does, what will you automatically wonder about? What other crystals are there, and what magic they do.

Solution: imply that your world contains more detail than is explicitly given in the book.

Conservation of detail: if something is explained in depth, it's because it's somehow important to the story. (The Malazan series by Steven Erikson stomp on this idea. He explains everything about everything.) Respect your readers' brain cells. If I ask the reader to spend a brain cell, there should be a reward for it.

Using the real world responsibly

How to avoid stereotypes

In real life we have stereotypes about entire nations, about some states or even some cities. In fantasy it is easy to fall into the same pattern. Elves have stereotypes about orcs and vice versa. Their races do not get along. But in reality, within any nation, people are quite different from one another. There is enough internal variation between elves and between orcs. In real world, your biggest beef is usually not with the person across the ocean, but with a person across the street. Your fantasy world will be more detailed if you tell us what elves fight among themselves about. Is it what type of wood is best for bow crafting? Is it something as silly as what end of an egg to open from breakfast?

What kinds of people tend to get left out this kind of story? Can you find a way to include them?

Going back to the vampires-in-a-zombie-apocalypse example, what kind of people don't make it through a zombie apocalypse? The elderly and the sick. One of Tex's friend had said: "Why would I want to read stories about apocalypse? If power goes out, my fridge goes out, I won't get my insulin and I'll die. So why would I want to read it?"

One of the plot threads in your book could be about how a guy with diabetes makes it through the apocalypse. Will the vampire take care of him personally? Will he the vampire hunt pigs to make insulin?

Make a story that includes a category of people who are not commonly included, and you might have a whole new big group of fandom for yourself.

Smash the Monoliths!

Question. What is the easiest, laziest, most obvious, least-realistic thing I could do with my fictional people?

Answer. Create a monoculture.

You are probably wondering: but what if I mess up? What if I write a character outside of my own experience and get it wrong? Don't worry, says Tex: you WILL mess up. No matter what you write, someone will hate it. There is a famous quote: "If you're not pissing someone off, you probably aren't doing anything important." Use your fear of hurting people (from other cultures or marginalized groups) to motivate you to do your research. Listen to people, and solicit feedback -- even painful feedback.

The following year I had the fortune to attend another of Tex Thompson's workshops, "Plate Tectonics Theory of Dialogue". It took place in Austin in July 2017, and focused on dialogue. Your characters are constantly in motion: they clash, collide, fold, buckle, shift. Good dialogue expresses all that. Here are some of the slides from the dialogue workshop


Sunday, October 29, 2017

Scott Aaronson at the Austin Quantum Computing meetup

We have heard that quantum computers are supposed to be much faster than classical ones. But what exactly does that mean, and why can't computers based on some other exotic physical models of computation be as fast? Scott Aaronson examined other models of computation and dispelled some popular myths about quantum computing at the Austin Quantum Computing meetup in May of 2017.

His talk might not have had a whole lot of new stuff for those who read his blog. It was a tour-de-fource of the topics he often addresses on his blog, and a synopsis of what a layperson needs to know about quantum computing. It was about what makes quantum computing so fascinating, but also how to keep your expectations of it realistic.

Scott started his talk with a look at some hypothetical alternative forms of computing. What physical models of computation would be alternative enough to violate the Extended Church-Turing thesis?

Church-Turing Thesis is closely related to the definition of computability: it says that all the computable functions are those and only those that could be computed by the Turing machine. Extended Church-Turing Thesis says that a Turing machine can simulate all other computers with at most a polynomial overhead. Are there forms of computing that challenge the extended Church-Turing thesis? On what kind of physics could a computer possibly be based to overturn it? Scott examined hypothetical computers based on exotic conditions where everyday laws of physics break down.

Relativity Computer

Scott's first example was a relativity computer. How come no one talks about relativity computer, he asks. The idea is simple: you start your computer working on some really hard problem, maybe NP-hard problem, and leave it on Earth, while you take off into space. From the computer's perspective, billions years have passed, the civilization has collapsed. But from your perspective, thanks to the relativistic time dilation, only ~ 20 years have passed. You come back and miraculously find your computer in the rubble, still connected to a power source, and you can read out an answer to your hard computational problem. So why hasn't anyone tried it? If you're worried that your friends will be dead in the distant future, just bring them on the spaceship with you.

Humor aside, the question is, would such a "relativity computer" (well, in this case the computer is ordinary, it's you travelling at a relativistic speed that makes the answer appear quickly) provide a fast solution to NP-complete problems? Would the problem be solved in polynomial time from your perspective?

The answer to that, Scott says, has to do with the amount of energy that would take to accelerate to relativistic speed. If you want to get an exponential speedup in only polynomial amount of time as experienced by you, you would have to accelerate so close to the speed of light that would take exponential amount of energy. So before your spaceship takes off, just fuelling it up would take exponential time.

It can sometimes seem like you could achieve exponential speedup for some problems by exploiting certain physical processes, but to really evaluate any such possibility you have to look at everything we know about physics, such as the energy involved in such a calculation.

Zeno's computer

Zeno's computer is a hypothetical computer in which each operation would take only half the time that it took for the previous operation. This scenario could occur at the so-called Omega Point. Omega Point is a theological notion, but according to some physicists, it could occur under some highly debatable conditions. (I don't think Scott mentioned Omega Point in his speech, I just remembered this trope because it seemed fitting.) For example, the founder of quantum computing, David Deutsch, envisions Omega Point happening near the time of the Big Crunch, as the universe oscilates faster and faster. By the time the universe collapses, the computations have achieved nearly infinite speed, and if you simulate the whole universe on the computational power of those oscillations, the world will never end for you. The closer the real thing comes towards the end, the faster the oscillations will go, the longer "subjective" time you'll be able to simulate. Here is a quote from the David Deutsch book "Fabric of Reality" where he discusses Omega Point. Scroll down to the paragraph "The key discovery in the omega-point theory...".

On the Omega Point computational substrate you would be able to solve NP-hard problems fast. But according to our best cosmological models, the universe is not going to end in the Big Crunch. Even aside from this particular scenario, Scott points out a fundamental problem with Zeno's computer. Zeno's computer relies on infinite amount of computational capacity, but any space-time region has only a finite number of information storage capacity. He says so in his own comment on his blog:

"Rahul #50:

Does Nature (or an existing proof) prevent undecidability in statements involving finite times / spaces / lattices & precision?

Mathematically, if we know that a problem only requires enumerating a finite list of possibilities, then essentially by definition that problem is computable. This is why, any time you see a new problem that's been proved at least as hard as the halting problem, that problem will always involve some element that goes to infinity (if the title and abstract aren't forthcoming about this, read the main text and see! ?? ).

Physically, it's conceivable that we could have lived in a universe where an infinite amount of stuff could get done in finite time (e.g., by what I call the "Zeno Computer," that does one step in 1 second, the next in 1/2 second, the next in 1/4 second, and so on). In such a universe, of course the halting problem could be solvable in finite time.

But the current conjecture in theoretical physics -- primarily because of the work of Jakob Bekenstein on black hole thermodynamics, which I blogged about before -- is that we don't live in such a universe. Rather, we seem to live in a universe that can be modeled as a quantum computer where each finite region of space stores at most ~1069 qubits per square meter of enclosing surface area (with the bound saturated only by black holes), and where those qubits are operated on at most ~1043 times per second. In such a universe, of course the halting problem would not be solvable."

Also, he says in an excerpt of his talk Big Numbers


While no one has tested this directly, it appears from current physics that there is a fundamental limit to speed, and that it's about 1043 operations per second, or one operation per Planck time. Likewise, it appears that there's a fundamental limit to the density with which information can be stored, and that it's about 1069 bits per square meter, or one bit per Planck area. (Surprisingly, the latter limit scales only with the surface area of a region, not with its volume.)

What would happen if you tried to build a faster computer than that, or a denser hard drive? The answer is: cycling through that many different states per second, or storing that many bits, would involve concentrating so much energy in so small a region, that the region would exceed what's called its Schwarzschild radius. If you don't know what that means, it's just a fancy way of saying that your computer would collapse to a black hole. I've always liked that as Nature's way of telling you not to do something!

One of the few things about quantum gravity that everybody agrees on, says Scott Aaronson, is that it places fundamental limits on how much computation you place in a bounded region.

Other models of computation based on physical world

Sometimes people suggest that soap bubbles could solve NP-hard problems in polynomial time just by finding the minimum surface when they are connected. Finding the minimum surface for connected soap bubbles is an NP-hard problem, but humans have observed that soap bubbles form a minimum surface very quickly, thus prompting the idea that a polynomial-time algorithm for finding the minimum surface does exist. And if we could encode an NP-hard problem as a soap bubble problem -- in effect "feeding" it to a soap bubble computer -- then we could solve them in polynomial time.

Scott Aaaronson giving a presentation at the Austin Quantum Computing meetup
Scott Aaaronson giving a presentation at the Austin Quantum Computing meetup

The problem with it is that bubbles do get stuck in local optima, says Scott. In other words, the surface they settle into is not guaranteed to be the absolute minimum but some kind of local minimum. Scott talks about it in more detail in his paper "NP-complete Problems and Physical Reality" (PDF).

In his teens, Scott experimented with the surfaces soap bubbles form. That was the closest in his life that he had ever been to an experimentalist. And in his experimments the bubbles got stuck in local optima. "But I haven't tried every possible brand of soap," Scott quipped.

Same is true about using protein folding for solving NP-complete problems. Finding optimal configuration for a protein can be modelled as NP-complete problem, and yet every cell in our bodies does it every second. Despite having been under enormous selection pressure to not get trapped in local optima, proteins still sometimes do that, and that can lead to prion- and amyloid-related illnesses.

That's the basic problem with all physics-based computations: systems in nature do get stuck in local optima. "This may sound silly," says Scott, "but every few months I get calls from popular science writers and they ask me, what about this? This violates Church-Turing thesis! But the things they suggest usually have the problems I mentioned."

When Scott Aaronson first heard about quantum computing as a teenager, he was similarly skeptical. He thought some physicist didn't understand Church-Turing thesis. So he had to find out about quantum mechanics for himself.

Does quantum computing bypass Extended Church-Turing thesis?

Does it? Skipping ahead, the smart people of the internet think it very likely does.

But back to Scott Aaronson's story. Setting out to learn quantum mechanics, Scott found out that quantum mechanics is not as hard to learn as it is commonly assumed. As he says, Quantum Mechanics turns out to be incredibly simple once you take the physics out of it. And no, he doesn't mean in a woo-woo New Agey sense. He adds: "The way I see it, it's a level below physics. It's an operating system that the rest of physics runs on as application. And what that OS is is probability theory with minus signs."

Scott Aaaronson's slide on quantum mechanics as probability with minus signs
Scott Aaaronson's slide on quantum mechanics as probability with minus signs. It shows the double slit experiment with a smiley-faced photon going through two slits and interfering with itself.

Probabilities with minus signs" is the concept of probability amplitude, which Scott has written about in more detail in this Quantum Computing Since Democritus series article. Here, Scott shows how the concept of probability amplitude (which is an entity that can be negative) explains the phenomenon of quantum interference. Interference is what causes some "paths" that lead to an observed outcome (e.g. photon going through either slit in the famous double-slit experiment) to cancel each other, because one has a plus sign, and the other has a minus sign.

"Probabilities as complex numbers come up in the double slit experiment," says Scott. "If I close off one of the slits, the photon appears in places where it doesn't want to appear before. By decreasing the number of choices, I can increase the likehood of an event. Physicists were eventually forced to say: the photon has some amplitude for going through the first slit, and some amplitude for going through the second slit. And amplitudes are complex numbers. You have to add the amplitudes of all the slots, and then take a square. That's a positive number."

This approach to quantum mechanics leads you to learning enough quantum mechanics from the "right angle" to understand quantum computing -- and you don't need differential equations and Schrodinger's wave equation to understand it. The latter is the traditional approach to teaching quantum mechanics, and, according to Scott, it scares people away from it. "Richard Feynman in his book "QED" doesn't even mention complex numbers. He says that each path has an arrow attached, and to compute how likely that path was, you stack those arrows together. So that's a perfect example how to boil it down to a bare minimum but not lower than that," says Scott. "I've given talks about this stuff at high schools. The smarter high school students can understand a lot of it without much difficulty, part of it because there is less they have to unlearn. To get into this field you don't have to take years and years of physics, you don't have to known how to do integrals or solve differential equations. But you have to understand vectors and matrices and complex numbers. So that's the bare minimum. But that bare minimum is accessible to a much larger population of people than the people that had been traditionally thought of as being able to understand quantum mechanics."

(To be fair, not all quantum physicists agree that quantum mechanics can be taught as "probability theory with minus signs" without first introducing the wave equation and such. Here is a discussion on Quora about what is lost when you approach it that way. -- E.)

Understanding interference will also inoculate you against the biggest fallacy that's being thrown around in the popular press when explaining quantum computing. A quantum computer does not "try every answer in parallel" to arrive at the right answer. If there is one thing Scott would like you to take away from this or any of his quantum computing presentations, it is this. The quantum computer does not try every answer in parallel. It's not a massively parallel classical computer.

It is interference that lets you get the right answer out of a quantum computer. You rely on the fact that amplitudes behave not like probabilities because they can cancel each other. For every wrong answer, you hope that each path leading to the answer to have equal positive and negative amplitudes, so they could cancel each other. For the right answer we want all the paths leading to it to have either all positive or all negative amplitudes. We need to to do something to boost the probability of the right answer, and quantum interference does that. That's one new tool quantum mechanics puts in our toolbox.

This is also his bare minimum standard for popular science articles explaining quantum computing, also known as the minus sign test. The article needs to mention interference.

Applications of quantum computing

Though we are used to thinking about quantum computers as something that would let us solve hard problems fast, the first application of quantum computing that its pioneers conceived wasn't that at all. Their initial reason for building quantum computers was to simulate quantum systems. "In the 1980s, Feynman, Deutsch, and others noticed that a system of n qubits seems to take ~ 2^n steps to simulate on a classical computer, because of the phenomenon of entanglement between the qubits. They had the amazing idea of building a quantum computer to overcome that problem," Scott says. And now, decades after Deutsch proposed that idea, Scott Aaronson still thinks that quantum simulation is a major, perhaps the biggest and most promising, application for quantum computing. It could have huge applications for energy.

For Scott personally, the number one application is to disprove people who come to his blog and argue that quantum computing is impossible.

What about cryptography?

When people say "quantum cryptography", they typically mean one of two things: (1) Quantum Key Distribution (QKD) -- a process that lets two parties exchange cryptographic keys while guaranteeing that the keys won't be intercepted by an attacker in transit, or (2) quantum-safe cryptography, that is to say, classical encryption algorithms that can't be broken by quantum computers any faster than they could be broken by classical computers. I'm not sure which one Scott meant when he said that quantum cryptography already exists today, but there is almost no market for it, because it's a problem that's already solved by private key encryption.

As far as public-private key encryption, it relies on computational difficulty of factoring large numbers, and that is actually vulnerable to Shor's factorization algorithm, but there are many symmetric encryption algorithms (that use the same key for encryption and decryption) that don't rely on factorization and thus can't be cracked by quantum computers.

(Here is a more detailed overview of quantum-safe encryption algorithms and QKD.)

But when it comes to using quantum computing to solve any kind of problems faster, as anyone who reads Scott's blog already knows, he is very doubtful that there will be real, practical applications for quantum computing in that respect. At least not soon.

Can quantum computers actually achieve exponential speedup? What about any other kind of significant speedup?

"If we were physicists, we would have declared P != NP to be a law of nature," Scott says. "But we use different terminology. Where physics have laws, we have conjectures."

Popular press sometimes states that quantum computers can solve NP-complete problems in polynomial time, but anyone who reads Scott's blog knows that's not true. The integer factorization problem that Shor's algorithm solves is not known to be NP-complete, and is suspected not to be. But can quantum computers do it at some point?

Scott Aaaronson's slide of the BQP problem class
Scott Aaaronson's slide of the BQP problem class

There is a complexity class called BQP, or bounded-error quantum polynomial time. Those are problems for which exists a bounded-error polynomial time algorithm for quantum computers. "Bounded error" means that the algorithm will give a wrong answer no more than a certain percentage of times -- that percentage probably being sufficiently low, or can be brought down to be sufficiently low for practical purposes. This class of problems is bigger than P, the class of polynomially-solvable problems, but it definitely does not include the NP-complete problems -- at least nobody at present thinks that it does, and there is a lot of evidence that it doesn't. So most likely polynomial-time algorithms for NP-complete problems, even on quantum computers, don't exist.

But it's not known yet where the boundaries of BQP lie. While it includes some problems in the intermediate zone of NP problems that are not known to be P, but not known to be NP-complete either, some of these problems are very special problems. We don't even know if BQP is contained in NP. So there may be problems that quantum computer can efficiently solve, but a classical computer might not even be able to verify the answer. For that you would need another quantum computer.

What about D-Wave's claims of exponential speedup?

D-Wave is a company that builds adiabatic quantum computers and that has claimed to achieve quantum supremacy, that is, made a quantum computer that achieves significant speedup over a classical computer for some type of problem. Scott has long been skeptical of their claims. Even if you were able to build a perfect adiabatics quantum computer, we don't know how well it would do. The quantum adiabatic algorithm was described in a 2000 paper by Farhi and other authors, and the general idea is shown in this slide by Scott. Farhi suggested that maybe it solves NP-complete problems in polynomial time, which would put NP in BQP. The iffy part is that the amount of time you need to run adiabatic algorithm depends on something called eigenvalue gap. As you vary the Hamiltonian, what is is the smallest gap between its first and second eigenvalues? If that gap becomes exponentially small, you need to run it for an exponential time. "And some people were able to construct problems for which this gap becomes exponentially small," says Scott.

"After you've seen problems with NP-completeness, you are tempted to elevated [computational] hardness as a fundamental physics problem. You would ask, what implication it would have for physics? And now we know some examples: for example, in condensed matter systems spectral gaps would have to become exponentially small," says Scott Aaraonson.

For the last some number of years D-Wave has been trying to find problems for which adiabatic algorithm would be exponentially faster than a classical algorithm. Scott is quite skeptical that they have found any. In the previous quantum computing meetup, though, Brian La Cour from UT Austin said he thought it wasn't so clear-cut, because the recent D-Wave advancements make it less apparent that there is a classical algorithm that would do just as well. But it's not that Scott is skeptical about adiabatic algorithms altogether. "We may not understand the potential of adiabatic algorithm until we have a real quantum computer," he says.

Scott Aaronson's areas of research

Scott's own research area is quantum supremacy, that is, finding quantum algorithms that for some types of problems provide a definite speedup over any classical algorithm. And by the way, he got a lot of comedic mileage out of that phrase during the Trump campaign year.

A year ago Scott wrote this paper connecting quantum computation to the black hole firewall problem. He briefly mentioned it and said that there wasn't enough time to discuss it at this presentation. This left me and some other people in the audience with a cliffhanger feeling. Just when we got to hearing something we had not heard about before, the lecture was over! Some of us asked Scott about that paper later after the talk, and he pointed us to more information about the paper on his blog.

Questions from the audience

Unfortunately, the questions were nearly impossible to hear, because the audience members didn't have a microphone. So I could only guess the general topic they asked about.

Q1. About quantum entanglement.

Scott Aaronson. I didn't say much about entanglement in this talk. In quantum mechanics entanglement is not a separate rule you have to postulate. It's just something that's there for a ride. It's just that entanglement means that in QM you can't write a state of a qubits as a product state.

If qubits are not entangled, you don't have a quantum computer. You can simulate it easily with a classical computer. Entanglement is a necessary but insufficient condition for QM.

Q2. About decoherence, the problem that makes quantum computing so hard to implement in practical terms.

Scott Aaronson. A crucial discovery from the nineties was that you don't have to get your decoherence rate down to 0. You just need to get it down to very very low rate. So even if some small number of qubits will leak out into environment, the quantum information that you care about is still there.

Q3. About machine learning and quantum computing.

Scott acknowledged that quantum computing might seem like a natural fit for quantum computing. "In a way, machine learning is all about linear algebra in high-dimensional spaces, and so is quantum computing. But you always have to ask, if someone can simulate a quantum machine learning algorithm with a classical approach, would they really a get a speedup from the quantum computing algorithm?"

Thursday, May 25, 2017

Advances in quantum computing: presentation by Dr. Brian La Cour

Dr. Brian La Cour from University of Texas at Austin gave a presentation on the latest state of quantum computing to Austin's Quantum Computing meetup in March of 2017. Here are some prominent points from it.

Several big companies are getting into quantum computing now: Google, Microsoft, IBM. There are significant differences between their approaches.

Google plans to solve a problem with 49 qubits, a problem that would demonstrate quantum supremacy (getting a clear speedup with a quantum algorithm over a classical algorithm), but is completely useless in real life. The problem with that is that when you progress to the quantum supremacy frontier, you can no longer check the answer with a regular device. Or it would take a very long time. So Google's argument will probably be based on asymptotic trend, with how they are doing with more qubits. But overall this problem of how to check the results will be more difficult in the future.

Brian La Cour talks at the Austin Quantum Computing meetup
Brian La Cour talks about Google's race to quantum supremacy at the Austin Quantum Computing meetup

We are a long way from solving Shor's algorithm and breaking internet's encryption. But quantum simulation is a near term application. It goes back to Richard Feynman's discussions of quantum computing. We can simulate things on a digital computer, but it's not very efficient. When you want to add another spin, another atom, you have to double the memory. What better thing to simulate a quantum system than a quantum system?

There is a difference between gate-based quantum computing (like what IBM and partially Google does) and quantum annealing, like what D-Wave does, and partially Google.

Gate-based device (that operates on gates, similar to classical gates) is a universal quantum computer. D-Wave's computer is specialized, it is only useful for certain optimization problems. And so far those problems have been pretty contrived, not necessarily corresponding to anything in real life. Even so there is no definitive evidence that the D-Wave's computer is advantageous for solving specific practical problems, as compared to classical solvers. There is a professor somewhere who, every time when D-Wave claimed that their quantum computer was solving some problems more efficiently, took it as a challenge to find a classical algorithm that would beat it. And so far he has been successful. But lately this has become less clear, because he has been, in Brian's words "exploiting what he knows about the problem". (Mathematicians and computer scientists can make it sound like it's a bad thing. But perhaps he means that while the professor is exploiting special knowledge about a problem, the quantum annealing computer can't make use of that knowledge, thus he is not comparing apples to apples? -- E.)

IARPA -- funding agency for intelligence community, analogy of DARPA -- is focused on developing next-generation quantum annealing, a universal quantum annealer. Their goal is, can you take benchmark projects and scale them to the thousands of qubits that D-Wave has?

Microsoft is looking at high-level languages for quantum computing. They are designing high-level languages that optimize what low-level languages do. They also do their own research into topological quantum computing, which is a very different approach than the qubit-based QC, but Brian thinks that's technologically so far away it's probably never going to happen.

This brings us to another Brian La Cour point, which is that now is a good time even for ordinary software developers to get involved in quantum computing, and you don't have to be a researcher to do it. There are people who are building interfaces in conventional programming languages to QASM, IBM's Quantum assembly language. This is where you as an individual can make a contribution: figure out how to do things in QASM and implement an interface to it in your favorite language. Also, individuals can play around with the IBM's Quantum Experience, a web interface to the IBM's quantum computer, and familiarity with it could put you in a position to get a job at some company that does quantum computing (not that there are many of those currently -- E.).

According to Brian, quantum gamification is also a trend. However, he used the word "gamification" not the way it is typically used (to incentivize certain user behaviors by making them seem like a game). He meant it more literally in the sense of games that teach you something about quantum mechanics. In some of those games people perform actions that help quantum researchers. Here are some examples:

  • qCraft -- a "mod" to the popular Minecraft game. It uses "quantum blocks" to teach superposition, observation, and entanglement.
  • There are even games that have been programmed on IBM Quantum Experience, such as Quantum Battleship.
  • Decodoku was developed to help researchers with quantum error correction. You are protecting researchers from errors.
  • cat-paper-scissors game (I could not find it by googling -- E.)
  • Quantum Cats from University of Waterloo, Canada. It's like angry birds, except cats can be in superpositions.

Brian La Cour noted that not only quantum computing research is strong in Canada, Canadian QC scientists also do a lot of educational outreach. US scientists don't do nearly as much, but they should.

As always, the least predictable part of any presentation is the audience's questions, and Brian got a few of those.

Audience member. Have you heard of neuromorphic computing?

Brian replied that he has heard about it, but that there wasn't any connection there to quantum computing. It was just another unconventional way to compute. Apropos of unconventional computing, quantum computing in a way is a throwback to analog computing: encoding information in continuous variables, except what comes out is still digital.

Audience member. Can quantum computing be used to mine bitcoins?

Aside from currently existing quantum computers being nowhere near powerful enough to mine bitcoins, Brian also noted that the value of bitcoin is based on the fact that bitcoins are computationally difficult to find. So if you find an algorithm to mine them fast and reliably, it will devalue them.

Audience member. How big a leap is it to go from classical programming to quantum programming? Is it a totally different beast?

Brian. It is a totally different beast. If you try to do things like conditionals and loops, you are doing it wrong. Instead of conditionals you have control gates, where value of one qubit controls what happens to another qubit. Which is sort of like conditional, but linear. A qubit in a superposition of 0/1 controls another qubit which is also in superposition.

The way you think about quantum computing is taking your entire data space, or state space, and think about it all at once.

You initialize all to 0 and apply Hadamard gates all at once. It puts them in superposition of all possible states, and then you do operation on them. You are looking at the whole haystack and apply operations to the whole haystack until you find a needle. You don't examine each value and look whether it's a needle.