December 4, 2021

Could quantum computers be cost-effective by 2036?

In theory, quantum computers could be much more efficient at some kinds of tasks, which could be potentially disruptive in applications areas such as cryptography. But you know: in theory, theory and practice are the same, but in practice, they are not. So it’s interesting to find applications where quantum computing might possibly be useful and cost-effective in the near(ish) future.

So let’s talk about cell-phone towers. A 5G base station contains a phased-array antenna, that is, a 2-d array of small antennas that can be aimed in a particular direction (for sending or receiving) by adjusting the phase of their signal. And with the superposition principle, this phased-array antenna can simultaneously aim one signal at your iPhone here, while aiming another signal at that Android phone over there, and hundreds more devices all at once. To do that the base station must compute a difficult (NP-complete) combinatorial optimization problem every few milliseconds, as the phones move around. This is called “Massive MIMO,” Massive Multiple-Input-Multiple-Output communication.

Why bother? Well, in dense and expensive cities, it’s so expensive to construct another cell-phone tower that it’s worth the cost of continuous heavy computation to optimize the number of simultaneous connections that each tower can handle. That cost is mostly in the electricity it takes to run a big high-powered compute server for the base station–both in dollars and in carbon footprint.

Recently my colleague Kyle Jamieson and his student Srikar Kasi published a couple of papers demonstrating that a commercially available Quantum Annealing computer, the D-Wave, can solve toy-scale MIMO antenna optimization problems. Unlike “gate model” quantum computers, which implement Von Neumann machines that can compute in a superposition of states, quantum annealing finds optimal or near-optimal solutions to node labeling on a weighted undirected graph. You might think that this is not very general, but plenty of real-world optimization problems can be encoded into this graph problem. And, more to the point: small-to-medium scale quantum annealing computers are practical and commercially available now, whereas gate-model quantum computers are not yet practical except at tiny scale.

But still, quantum annealing computers (such as the D-Wave) are expensive, and require special refrigeration units to get them down to 15 milliKelvin. Could there really be an application where it’s more cost-effective to buy one of those, instead of just a rack full of Arm servers?

Massive MIMO, the antenna-aiming problem, is a good candidate: it demands that the same specialized NP-complete problem be solved every millisecond; and improving the optimization means that more cell-phone conversations can be handled by the same expensive cell tower.

A new paper by Srikar Kasi and colleagues at Princeton, InterDigital, and University College London tries to answer the question, “based on current trends in the improvement of commercially shipped quantum annealing hardware, how many years in the future will be it cheaper to run a quantum annealer than to run a rack full of conventional servers?” And the answer is, maybe in the range 2027-2036 the two solutions will be equally cost-effective for medium-large cellular base stations. And maybe after 2036 the quantum annealer will consume 45% less electricity (be 45% cheaper to run) than conventional computers for large cellular base stations.

That’s pretty exciting. Because up to now I thought that quantum computing is the technology of the future and always will be. But 2036 is only fifteen years away, and maybe we’ll really see this happen.

Additional remark: Quantum simulators are another kind of special-purpose (not gate-model) soon-or-now practical quantum computer. What I find interesting about Massive MIMO is that the quantum computer is solving a combinatorial optimization problem that is not directly about quantum mechanics.

Another 2020 lawsuit over internet voting

Last week I summarized 4 lawsuits filed in 2020 over internet voting, in VA, NJ, NY, NH. Then I learned there was another in North Carolina.

In 2020 the North Carolina Council of the Blind sued the State Board of Elections, demanding that the Board offer “alternative format absentee ballots allowing private and independent method of absentee ballots that is accessible for Plaintiffs and others with vision disabilities.”

The Plaintiffs did not specifically demand internet ballot return. Instead, they demanded compliance with the Americans for Disabilities Act that requires “reasonable modifications in the Absentee Voting Program to avoid discrimination against Plaintiffs on the basis of disability.” The Plaintiffs also explained methods that other states were already using to accomplish this [all excerpted verbatim from the Complaint]:

  • Maryland developed an online marking tool that allows voters to access and mark their absentee ballots on their computers. . . . Although the absentee ballot must still be printed, signed, and returned to the voter’s local board of election, voters need not sacrifice the secrecy of their ballots to receive assistance with signing because the signature page prints separately from the ballot.
  • Oregon, Wisconsin, and New Hampshire have employed an accessible electronic voting system that can be used for both in-person and absentee voting. Using the platform, voters can access their absentee ballots through their web browser and mark their ballots on their computers. Voters then print their ballots and mail them back to their local boards of election where their votes are counted. … The platform used by these states has been released as open source technology, meaning that it can be used by the NCSBOE, or by any other entity, free of charge.
  • West Virginia has similarly provided an electronic absentee ballot delivery and marking tool to voters with disabilities. Voters access the electronic absentee ballot tool via a web portal, where they are guided with on-screen instructions on how to open and complete the electronic ballot. After completing the ballot, West Virginia law provides that qualifying voters may either (1) print and mail their absentee ballot to their county clerk, or (2) submit their absentee ballot electronically to their county clerk directly through the web portal.
  • Alaska [has] have provided accessible remote voting options for some elections . . . an electronic absentee ballot that can be completed and transmitted using the voter’s computer.
  • Michigan made its UOCAVA PDF ballots accessible and available to blind voters . . . [but no electronic return of voted ballots]
  • New York . . . agreed to email accessible absentee ballots to qualified voters with disabilities [but no electronic return of voted ballots]

In summary, the Complaint laid out a variety of ways in which other states had complied with the ADA, but did not specifically request internet ballot return. The motion for preliminary injunction was similarly open-ended.

The Court, apparently, felt that such an open-ended injunction would be difficult to enforce. And apparently North Carolina was already using Democracy Live’s system for UOCAVA voters, and said so in court. So the Court’s order read, “Defendants are hereby ORDERED to open the Democracy Live portal to plaintiffs and other blind voters as expeditiously as possible so that it may be utilized for the November 3, 2020 election.”

A year later, in August 2021, the State agreed to settle the case, having agreed to use the Democracy Live “accessible electronic voting portal” through which “the State Board provides visually impaired voters the ability to request to vote absentee, to mark their absentee ballots, and to return their absentee ballots.” In addition they “identified . . . vendors who are capable providing Large Print, Braille, or accessible electronic formats of absentee ballots and other communications related to voting processes.”

Judge Boyle’s final judgment omits any mention of Democracy Live, and orders “The North Carolina State Board of Elections (“NCSBE”) shall ensure that blind voters can request, mark, and return their absentee ballot through accessible electronic means in the 2021 municipal elections (whenever held) and in all subsequent elections.” (emphasis mine) So it appears that internet voting for blind voters in North Carolina currently has the force of law behind it.

It’s too bad that an opportunity was lost here. Last week I wrote, “it would be a good idea for the National Federation of the Blind to remove internet ballot return from its set of demands, and focus on the other reasonable and practical reforms that they have been requesting (or suing for).” And here is a case where the North Carolina Council for the Blind had already done just what I suggested, demanding “reasonable modifications in the Absentee Ballot program” but not specifically demanding the insecure, unsafe, unverifiable extreme of internet ballot return.

The North Carolina State Board of Elections then unnecessarily chose to include internet voting in their response, because their vendor (Democracy Live) made that convenient for them. (Democracy Live does that even more insecurely than you might have imagined! And each of their competitors does internet voting insecurely in its own surprising way!) And then Judge Boyle enshrined this expedient into an Order.

I am not a lawyer. But a lawyer friend writes: This judgment is only a legal way station; don’t assume this is anything near a permanent order, if other evidence is later adduced undermining its soundness. And really, the Plaintiffs’ initial motion was very poor lawyering in one critical respect: the request for “reasonable modifications” with examples from other States was basically punting to the Federal Judge to do their thinking for them, for the court to supply the terms for a precise order that for some inexplicable reason, they did not craft and then support in their brief.  It’s not surprising that, given the lack of expertise in the federal courts on internet voting insecurity, election security ambiguities, and various NC election administrative requirements, that the court (likely law clerks) jumped to the Democracy Live solution, which NC had already adopted for a different purpose.

Four 2020 lawsuits over internet voting

Citizens with disabilities (and voters living abroad) must have the substantive right to vote—that’s the law.  Sometimes that turns into a demand for internet voting.  But as I wrote earlier this year, internet voting is dangerously insecure, it’s not what most voters with disabilities want, and there are much better ways of accommodating voters with disabilities, and the states should implement those accommodations.

Last year saw several lawsuits demanding internet voting as an accommodation—that is, the return of voted ballots by internet.  The most recent of these (in New Hampshire) was just recently settled. 

  • In 2020, the National Federation for the Blind sued the State of Virginia asking for internet voting (and other accommodations for voters with disabilities).  The parties settled for no internet voting, but other accommodations for voters with disabilities.
  • In 2020, New Jersey quietly took steps to allow internet voting, were sued on the basis that this would be both insecure and illegal; and then agreed not to pursue internet voting in New Jersey, but to use other means to accommodate voters with disabilities.
  • In 2020, a group of plaintiffs living abroad sued 7 states in U.S. District Court asking for internet voting.  The court denied their request for a preliminary injunction, and then the plaintiffs moved to dismiss the case.
  • In 2020, the National Federation for the Blind sued the State of New Hampshire asking for internet voting, and for accessibility improvements in the State’s election website (that provides information for voters).  The parties settled for no internet voting, but other accommodations for voters with disabilities (some of which New Hampshire already had in place), and for improvements in the web site.

There’s a pattern here.  The courts have not recognized a right to vote by internet; these States have declined to adopt this insecure method of voting; and these States have been willing to adopt other reasonable accommodations for voters with disabilities.

Perhaps it would be a good idea for the NFB to remove internet ballot return from its set of demands, and focus on the other reasonable and practical reforms that they have been requesting (or suing for):  Make websites accessible, improve procedures in the way voters with Print Disabilities are permitted to prepare and return their ballots, and perhaps some of the improvements suggested by Noel Runyan at the end of my previous article.

Added shortly after publication: It has come to my attention that there was a fifth 2020 lawsuit, Taliaferro et al. v. North Carolina State Board of Elections. I’ll write about that in a future article.