Connect with us


All the companies from Y Combinators W20 Demo Day, Part III: Hardware, Robots, AI and Developer Tools




Y Combinator’s Demo Day was a bit different this time around.

As concerns grew over the spread of COVID-19, Y Combinator shifted the event format away from the two-day gathering in San Francisco we’ve gotten used to, instead opting to have its entire class debut to invited investors and media via YC’s Demo Day website.

In a bit of a surprise twist, YC also moved Demo Day forward one week, citing accelerated pacing from investors. Alas, this meant switching up its plan for each company to have a recorded pitch on the Demo Day website; instead, each company pitched via slides, a few paragraphs outlining what they’re doing and the traction they’re seeing, and team bios. It’s unclear so far how this new format — in combination with the rapidly evolving investment climate — will impact this class.

As we do with each class, we’ve collected our notes on each company based on information gathered from their pitches, websites and, in some cases, our earlier coverage of them.

To make things a bit easier to read, we’ve split things up by category rather than have it be one huge wall of text. These are the companies that are working on hardware, robotics, AI, machine learning or tools for developers. You can find the other categories (such as biotech, consumer, and fintech) here.

AI and Machine Learning

Datasaur: A tool meant to help humans label machine data data sets more accurately and efficiently through things like auto-correct, auto-suggest and keyboard hotkeys. It’s free for individual labelers, $100 per month for teams of up to 20 labelers, with custom pricing for larger teams.

1build: Automatic, data-driven job cost estimates for construction companies. You upload your plans, and 1build says it can prepare accurate bids “in minutes.” The company projects a revenue run rate of over $600,000, and says it has completed estimates for mega companies like Amazon, Starbucks and 7-Eleven.

Handl: An API for turning paper documents — including handwritten ones — into structured data ready to be plunked into a database or CRM. While the company says that around 85% of its processing is handled by their AI, it’s backed by humans to validate data when the AI’s confidence is low. Nine months after launch, the company is seeing an ARR of $0.9 million.

Zumo Labs: Uses game engines to generate pre-labeled training data for computer vision systems. By synthesizing the data rather than collecting it from photos/videos of the real world, the company says it can create massive data sets faster, cheaper and without privacy issues.

Teleo: Retrofits existing construction equipment to allow operators to control them remotely. The company says it has built a “fully functional teleoperated loader” since being founded three months ago, and plans to charge construction companies a flat monthly fee per vehicle. The company’s co-founders were previously head of Hardware Engineering and director of Product Manager at Lyft, with both having worked on Google’s Street View team.

Menten AI: Menten AI says it’s using “quantum computing and machine learning” combined with synthetic biology to design new protein-based drugs.

Turing Labs Inc.: Automated, simulated testing of different formulas for consumer goods like soaps and deodorant. Home products and cosmetics can be months of work for R&D labs. Turing has built an AI engine that helps with this process — much like the AI engines used in drug discovery — cutting down the time to days. It’s already working with some of the biggest CPG companies in the world. You can find our previous coverage on Turing here.

Segmed: Segmed is building data sets for AI-driven medical research. Rather than requiring each and every researcher to individually partner with hospitals and imaging facilities, Segmed partners with these organizations (currently over 50) and standardizes, labels and anonymizes the data.

Ardis AI: Ardis AI wants to build the foundation of artificial general intelligence — technology that read and comprehend text like a human. By combining neural networks, symbolic reasoning and new natural language processing techniques, Ardis AI can serve companies that don’t want to hire teams to do data extraction and labeling.

Agnoris: Agnoris analyzes a restaurant’s point-of-sale data to recommend changes to pricing, delivery menus and staffing. For $3,600 per year per restaurant location, Agnoris claims to be able to raise profits by 20%. The company started after the founder opened a restaurant that was packed yet losing money, so it built machine learning tools to improve margins and now it’s selling that software to all eateries.

Froglabs: Froglabs provides weather forecasting AI to businesses for predicting solar and wind energy production, delivery delays, staffing shortages, sales demand and food availability. By ingesting petabytes of weather data, it can save companies money by ensuring their logistics aren’t disrupted. Founded by a long-time Googler who started its Project Loon internet-beaming weather balloons, it’s now signing up e-commerce, retail, rideshare, restaurant and event businesses.

PillarPlus: PillarPlus is a platform that automates the blueprint-designing phase of a building project. It takes a design from an architect or contractor and maps out mechanical, fire, electrical and plumbing details, and estimates the bill of materials and project cost, steps that otherwise take months of work.

Glisten: Glisten uses computer vision and machine learning technologies to develop better, more consistent data sets for e-commerce companies. Its first product is an AI-based tool to populate and enrich sparse product data. Find our previous coverage of Glisten here.

nextmv: Nextmv gives its customers the ability to create their own logistics algorithms automatically — allowing businesses to optimize fleets and manage routes internally.

Visual One: Movement-detecting security cameras can bring up a lot of false positives: there’s motion, yes, but not necessarily anything harmful. Visual One has built an AI platform that integrates with home security cameras to “read” the specific movements that they detect. Owners can create customised alerts so they get notifications only for what they care about. The company’s software can check for furniture-destroying pets, package-lifting thieves, the death-defying antics of toddlers and more. Find our previous coverage of Visual One here.

PostEra: “Medicinal chemistry-as-a-service” is the idea here: PostEra’s platform can design and synthesize molecules faster and at a lower cost than the typical R&D lab, speeding up the research time it takes to test new combinations in the drug discovery process.

Hardware and Robotics

Cyberdontics: Robotics have already revolutionized surgery, courtesy of companies like da Vinci-maker, Intuitive. Cyberdontics is aimed at doing the same for oral surgery, beginning with crowns — one of the more expensive and time-intensive procedures. The company says its robot is capable of performing the generally two-hour procedure in 15 minutes, charging a mere $140 for the job.

Avion: Focused on inhabitants of difficult to reach areas in Africa, Avion is building a drone-based delivery system. The plans consist of medium and long-range medical drones tied to a centralized hub. The drones are hybrid and autonomous with vertical take-off capabilities, able to take 5-kg payloads as far as 150 kms.

SOMATIC: Industrial bathroom cleaning is a prime “dull”/“dirty” candidate to be replaced by automation. Somatic builds large robots that are trained to clean restrooms via VR. The system sprays and wipes down surfaces and is capable of opening doors and riding up and down in the elevator. Find our previous coverage of SOMATIC here.

RoboTire: Anyone who’s ever sat in a service shop waiting room knows how time-intensive the process can be. RoboTire promises to cut the wait time from 60 minutes down to 10 for a set of four tires. The company has begun piloting the technology in locations around the U.S. Find our previous coverage of RoboTire here.

Morphle: Designed to replace outdated analog microscopes, Morphle’s system uses robotic automation to improve imaging. The startup processes higher-resolution images than far pricier systems and with a much smaller failure rate. Morphle has begun selling its system to labs in India.

Daedalus: Founded by an early engineer at OpenAI, Daedalus is building autonomous software to allow industrial robots to operate without human programming, beginning with CNC machines. The company projects that it can improve productivity in the metal machining market by 5x.

Exosonic, Inc.: Exosonic makes supersonic commercial aircraft that don’t have to produce a loud sonic boom, so they can be flown over land. Its goal is a plane that can fly from SF to NYC in three hours. The CEO worked on NASA’s low-boom X-59 aircraft while at Lockheed Martin. Exosonic now has letters of intent from a major airline and two Department of Defense groups, plus a $300,000 U.S. Air Force contract.

Nimbus: Founded by a serial entrepreneur and based in Ann Arbor, Mich., Nimbus is developing the next-generation vehicle platform for urban transportation. Founder Lihang Nong previously launched the fuel-injection systems developer PicoSpray and is now looking to answer the question, “Can a vehicle be several times more space and energy efficient than today’s cars while actually being more comfortable to ride in?”

UrbanKisaan: UrbanKisaan is a vertical farming operation based in India that delivers fresh produce subscriptions to households. Its farms of stacked-up hydroponic tables can be located near cities with just 1% of the land usage of traditional agriculture, and there are no pesticides necessary. In a market with a growing middle class seeking healthy foods, delivering from farm-to-door could let UrbanKisaan control quality and its margins.

Talyn Air: Two former SpaceX engineers have developed a long-range electric vertical take-off and landing (eVTOL) aircraft for passengers and cargo. The startup has created an electric fixed-wing aircraft that is caught mid-air with a custom winged drone during take offs and landings, an approach that its founders say give this aircraft three times the range of its competitors, at 350 miles.

Developer Tools

BuildBuddy: Two ex-Googlers want to provide a “Google-style development environment” to all by building an open-source UI/feature set on top of Google’s Bazel software. The company says that their solution speeds up build times by up to 10x. It’s free for independent developers, with the price scaling from $4 per user to $49 per user depending on the size of the team and the features required.

Dataline: Meant to let websites gather analytics data from users who are using ad-blocking tools. Claiming that most ad-blocker users care mostly about display ads or cross-site tracking, the company says that first-party analytics gets hit as “collateral damage.” By acting as a “smart proxy” that runs on a sub-domain, Dataline avoids most ad-blocking systems (for now, presumably.)

Cortex: Many modern online software applications are powered by countless independent, purpose-focused tools — or “microservices.” Cortex monitors your app’s microservices to automatically flag the right person (hooking into Datadog/Slack/PagerDuty/etc.) when one breaks.

apitracker: Even if your website seems to be loading fine, the APIs you use to make it work might be having trouble, breaking things in not so obvious ways. Apitracker… tracks your APIs. It monitors the APIs you use, alerting you when one of them starts to fail and providing insights into their overall performance.

Freshpaint: Freshpaint’s “autotrack” system collects all pageviews/clicks/etc. across your site, allowing you to push it into tools like Google Analytics/Facebook Pixel etc. retroactively without requiring your dev team to make manual trackers for each event. The base plan is free for sites with fewer than 3,000 users and $300 for sites with up to 50,000 monthly users, after which point the pricing shifts to custom packaging.

Datree: Datree allows companies to set up rules and security policies for their codebase, and ensures those rules are followed before any code is merged. Charging $28 per developer (noting that it’s free for independent/open source projects), they’ve pulled in ~$230K in revenue to date. Find our previous coverage of Datree here. Deploys your app on servers that are physically closer to your users, decreasing latency and improving the user experience. If your app grows more popular in a certain city, Fly detects that and scales resources accordingly.

Sweeps: Sweeps claims that they can make your website 40% faster with one line of code, by more intelligently loading all of the third-party tools that a website is using. The team says that their tech not only improves speed but does so while improving SEO.

Orbiter: Orbiter is an automatic real-time monitoring and alert system integrated with Slack to ensure better customer service and revenue management.

Release: Product releases can be tricky. Release provides a staging management toolkit — it builds a staging environment each time there’s a pull request, allowing for faster/more collaborative development cycles.

Signadot: Signadot is monitoring and management software for the microservices that modern startups rely on to power their own applications and services, hopefully flagging issues before they become apparent to the end user.

Raycast: Raycast is a universal command bar for developers and many of the tools they use. Users can integrate apps including Jira, GitHub or Slack and take a Superhuman-like approach to completing forms and tasks. The team is pitching the tool as a way to help engineers get their non-engineering work done quickly.

Cotter: Cotter is building a phone number-based login platform that authenticates a user’s device in a workflow that the company’s founders say has the convenience of SMS-based OTP without the security issues. The startup is aiming to target customers in developing countries where email is less utilized and less convenient as a login.

ditto: Ditto’s founders are hoping to create the Figma for words, helping teams plan out more thoughtfully the copy they use to describe their products and workflows. The collaboration tool created by Stanford roommates Jolena Ma and Jessica Ouyang currently has 80+ different companies represented among their users.

Scout: A continuous integration and deployment toolkit for machine learning experiments inside a GitHub workflow.

ToDesktop: ToDesktop has designed a service to automate all of your desktop application publishing needs. It works with Windows, Mac and Linux and provides native installers, auto-updates, code signing and crash reports without the need for any infrastructure or configurations for developers.

DeepSource: DeepSource is a code review tool that allows developers to check for bug risks, anti-patterns, performance issues and security flaws in Python and Go.

Flowbot: Flowbot is a natural language, autocomplete search tool for coding in Python. It lets Python developers type in plain English when they can’t remember the exact function they’re thinking of, with Flowbot digging through documentation and considering the context to find the code it thinks you’re looking for.

PostHog: PostHog is a software service that lets developers understand how their users are actually working with their products. It’s a product analytics toolkit for open-source programmers.

Read more:


What can you do in 48 hours?




Have you ever wondered what can be done in 48 hours? For instance, our heart beats around 200 000 times. One of the biggest supercomputers crunches petabytes (peta = 1015) of numbers to simulate an experiment that took Google’s quantum processor only 300 seconds to run. In 48 hours, one can also participate in the Sciathon with almost 500 young researchers from more than 80 countries! 

Two weeks ago I participated in a scientific marathon, the Sciathon. The structure of this event roughly resembled a hackathon. I am sure many readers are familiar with the idea of a hackathon from personal experience. For those unfamiliar — a hackathon is an intense collaborative event, usually organized over the weekend, during which people with different backgrounds work in groups to create prototypes of functioning software or hardware. For me, it was the very first time to have firsthand experience with a hackathon-like event!

The Sciathon was organized by the Lindau Nobel Laureate Meetings (more about the meetings with Nobel laureates, which happen annually in the lovely German town of Lindau, in another blogpost, I promise!) This year, unfortunately, the face-to-face meeting in Lindau was postponed until the summer of 2021. Instead, the Lindau Nobel Laureate Meetings alumni and this year’s would-be attendees had an opportunity to gather for the Sciathon, as well as the Online Science Days earlier this week, during which the best Sciathon projects were presented.

The participants of the Sciathon could choose to contribute new views, perspectives and solutions to three main topics: Lindau Guidelines, Communicating Climate Change and Capitalism After Corona. The first topic concerned an open, cooperative science community where data and knowledge are freely shared, the second — how scientists could show that the climate crisis is just as big a threat as the SARS-CoV-19 virus, and the last — how to remodel our current economic systems so that they are more robust to unexpected sudden crises. More detailed descriptions of each topic can be found on the official Sciathon webpage.

My group of ten eager scientists, mostly physicists, from master students to postdoctoral researchers, focused on the first topic. In particular, our goal was to develop a method of familiarizing high school students with the basics of quantum information and computation. We envisioned creating an online notebook, where an engaging story would be intertwined with interactive blocks of Python code utilizing the open-source quantum computing toolkit Qiskit. This hands-on approach would enable students to play with quantum systems described in the story-line by simply running the pre-programmed commands with a click of the mouse and then observe how “experiment” matches “the theory”. We decided to work with a system comprising one or two qubits and explain such fundamental concepts in quantum physics as superposition, entanglement and measurement. The last missing part was a captivating story.

The story we came up with involved two good friends from the lab, Miss Schrödinger and Miss Pauli, as well as their kittens, Alice and Bob. At first, Alice and Bob seemed to be ordinary cats, however whenever they sipped quantum milk, they would turn into quantum cats, or as quantum physicists would say — kets. Do I have to remind the reader that a quantum cat, unlike an ordinary one, could be both awake and asleep at the same time?

Miss Schrödinger was a proud cat owner who not only loved her cat, but also would take hundreds of pictures of Alice and eagerly upload them on social media. Much to Miss Schrödinger’s surprise, none of the pictures showed Alice partly awake and partly asleep — the ket would always collapse to the cat awake or the cat asleep! Every now and then, Miss Pauli would come to visit Miss Schrödinger and bring her own cat Bob. While the good friends were chit-chatting over a cup of afternoon tea, the cats sipped a bit of quantum milk and started to play with a ball of wool, resulting in a cute mess of two kittens tangled up in wool. Every time after coming back home, Miss Pauli would take a picture of Bob and share it with Miss Schrödinger, who would obviously also take a picture of Alice. After a while, the young scientists started to notice some strange correlations between the states of their cats… 

The adventures of Miss Schrödinger and her cat continue! For those interested, you can watch a short video about our project! 

Overall, I can say that I had a lot of fun participating in the Sciathon. It was an intense yet extremely gratifying event. In addition to the obvious difficulty of racing against the clock, our group also had to struggle with coordinating video calls between group members scattered across three almost equidistant time zones — Eastern Australian, Central European and Central US! During the Sciathon I had a chance to interact with other science enthusiasts from different backgrounds and work on something from outside my area of expertise. I would strongly encourage anyone to participate in hackathon-like events to break the daily routine, particularly monotonous during the lockdown, and unleash one’s creative spirit. Such events can also be viewed as an opportunity to communicate science and scientific progress to the public. Lastly, I would like to thank other members of my team — collaborating with you during the Sciathon was a blast!

During the Sciathon, we had many brainstorming sessions. You can see most of the members of my group in this video call (from left to right, top to bottom): Shuang, myself, Martin, Kyle, Hadewijch, Saskia, Michael and Bartłomiej. The team also included Ahmed and Watcharaphol.


Continue Reading


Optimal probes and error-correction schemes in multi-parameter quantum metrology




Wojciech Górecki1, Sisi Zhou2,3,4, Liang Jiang2,3,4, and Rafał Demkowicz-Dobrzański1

1Faculty of Physics, University of Warsaw, Pasteura 5, 02-093 Warsaw, Poland
2Departments of Applied Physics and Physics, Yale University, New Haven, Connecticut 06511, USA
3Yale Quantum Institute, Yale University, New Haven, Connecticut 06511, USA
4Pritzker School of Molecular Engineering, University of Chicago, Chicago, IL 60637, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We derive a necessary and sufficient condition for the possibility of achieving the Heisenberg scaling in general adaptive multi-parameter estimation schemes in presence of Markovian noise. In situations where the Heisenberg scaling is achievable, we provide a semidefinite program to identify the optimal quantum error correcting (QEC) protocol that yields the best estimation precision. We overcome the technical challenges associated with potential incompatibility of the measurement optimally extracting information on different parameters by utilizing the Holevo Cramér-Rao (HCR) bound for pure states. We provide examples of significant advantages offered by our joint-QEC protocols, that sense all the parameters utilizing a single error-corrected subspace, over separate-QEC protocols where each parameter is effectively sensed in a separate subspace.

► BibTeX data

► References

[1] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum metrology, Phys. Rev. Lett. 96, 010401 (2006).

[2] M. G. A. Paris, Quantum estimation for quantum technologies, Int. J. Quantum Inf. 07, 125 (2009).

[3] V. Giovannetti, S. Lloyd, and L. Maccone, Advances in quantum metrology, Nat. Photonics 5, 222 (2011).

[4] G. Toth and I. Apellaniz, Quantum metrology from a quantum information science perspective, J. Phys. A: Math. Theor. 47, 424006 (2014).

[5] R. Demkowicz-Dobrzański, M. Jarzyna, and J. Kołodyński, in Prog. Optics, Vol. 60, edited by E. Wolf (Elsevier, 2015) pp. 345–435.

[6] R. Schnabel, Squeezed states of light and their applications in laser interferometers, Phys. Rep. 684, 1 (2017).

[7] C. L. Degen, F. Reinhard, and P. Cappellaro, Quantum sensing, Rev. Mod. Phys. 89, 035002 (2017).

[8] L. Pezzè, A. Smerzi, M. K. Oberthaler, R. Schmied, and P. Treutlein, Quantum metrology with nonclassical states of atomic ensembles, Rev. Mod. Phys. 90, 035005 (2018).

[9] S. Pirandola, B. R. Bardhan, T. Gehring, C. Weedbrook, and S. Lloyd, Advances in photonic quantum sensing, Nat. Photonics 12, 724 (2018).

[10] C. M. Caves, Quantum-mechanical noise in an interferometer, Phys. Rev. D 23, 1693 (1981).

[11] M. Holland and K. Burnett, Interferometric detection of optical phase shifts at the heisenberg limit, Phys. Rev. Lett. 71, 1355 (1993).

[12] H. Lee, P. Kok, and J. P. Dowling, A quantum rosetta stone for interferometry, J. Mod. Optic. 49, 2325 (2002).

[13] D. Wineland, J. Bollinger, W. Itano, F. Moore, and D. Heinzen, Spin squeezing and reduced quantum noise in spectroscopy, Phys. Rev. A 46, R6797 (1992).

[14] K. McKenzie, D. A. Shaddock, D. E. McClelland, B. C. Buchler, and P. K. Lam, Experimental demonstration of a squeezing-enhanced power-recycled michelson interferometer for gravitational wave detection, Phys. Rev. Lett. 88, 231102 (2002).

[15] J. Bollinger, W. M. Itano, D. Wineland, and D. Heinzen, Optimal frequency measurements with maximally correlated states, Phys. Rev. A 54, R4649 (1996).

[16] D. Leibfried, M. Barrett, T. Schaetz, J. Britton, J. Chiaverini, W. Itano, J. Jost, C. Langer, and D. Wineland, Toward heisenberg-limited spectroscopy with multiparticle entangled states, Science 304, 1476 (2004).

[17] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum-enhanced measurements: beating the standard quantum limit, Science 306, 1330 (2004).

[18] S. F. Huelga, C. Macchiavello, T. Pellizzari, A. K. Ekert, M. B. Plenio, and J. I. Cirac, Improvement of frequency standards with quantum entanglement, Phys. Rev. Lett. 79, 3865 (1997).

[19] D. W. Berry and H. M. Wiseman, Optimal states and almost optimal adaptive measurements for quantum interferometry, Phys. Rev. Lett. 85, 5098 (2000).

[20] M. de Burgh and S. D. Bartlett, Quantum methods for clock synchronization: Beating the standard quantum limit without entanglement, Phys. Rev. A 72, 042301 (2005).

[21] A. Fujiwara and H. Imai, A fibre bundle over manifolds of quantum channels and its application to quantum statistics, J. Phys. A: Math. Theor. 41, 255304 (2008).

[22] R. Demkowicz-Dobrzański, U. Dorner, B. Smith, J. Lundeen, W. Wasilewski, K. Banaszek, and I. Walmsley, Quantum phase estimation with lossy interferometers, Phys. Rev. A 80, 013825 (2009).

[23] B. Escher, R. de Matos Filho, and L. Davidovich, General framework for estimating the ultimate precision limit in noisy quantum-enhanced metrology, Nat. Phys. 7, 406 (2011).

[24] R. Demkowicz-Dobrzański, J. Kołodyński, and M. Guţă, The elusive heisenberg limit in quantum-enhanced metrology, Nat. Commun. 3, 1063 (2012).

[25] J. Kołodyński and R. Demkowicz-Dobrzański, Efficient tools for quantum metrology with uncorrelated noise, New J. Phys. 15, 073043 (2013).

[26] S. I. Knysh, E. H. Chen, and G. A. Durkin, True limits to precision via unique quantum probe, arXiv:1402.0495 (2014).

[27] R. Demkowicz-Dobrzański and L. Maccone, Using entanglement against noise in quantum metrology, Phys. Rev. Lett. 113, 250801 (2014).

[28] E. M. Kessler, I. Lovchinsky, A. O. Sushkov, and M. D. Lukin, Quantum error correction for metrology, Phys. Rev. Lett. 112, 150802 (2014).

[29] W. Dür, M. Skotiniotis, F. Froewis, and B. Kraus, Improved quantum metrology using quantum error correction, Phys. Rev. Lett. 112, 080801 (2014).

[30] R. Ozeri, Heisenberg limited metrology using quantum error-correction codes. arXiv:1310.3432 (2013).

[31] G. Arrad, Y. Vinkler, D. Aharonov, and A. Retzker, Increasing sensing resolution with error correction, Phys. Rev. Lett. 112, 150801 (2014).

[32] T. Unden, P. Balasubramanian, D. Louzon, Y. Vinkler, M. B. Plenio, M. Markham, D. Twitchen, A. Stacey, I. Lovchinsky, A. O. Sushkov, et al., Quantum metrology enhanced by repetitive quantum error correction, Phys. Rev. Lett. 116, 230502 (2016).

[33] F. Reiter, A. S. Sørensen, P. Zoller, and C. A. Muschik, Dissipative quantum error correction and application to quantum sensing with trapped ions, Nat. Commun. 8, 1822 (2017).

[34] P. Sekatski, M. Skotiniotis, J. Kołodyński, and W. Dür, Quantum metrology with full and fast quantum control, Quantum 1, 27 (2017).

[35] R. Demkowicz-Dobrzański, J. Czajkowski, and P. Sekatski, Adaptive quantum metrology under general markovian noise, Phys. Rev. X 7, 041009 (2017).

[36] S. Zhou, M. Zhang, J. Preskill, and L. Jiang, Achieving the heisenberg limit in quantum metrology using quantum error correction, Nat. Commun. 9, 78 (2018).

[37] D. Layden and P. Cappellaro, Spatial noise filtering through error correction for quantum sensing, npj Quantum Inf. 4, 30 (2018).

[38] D. Layden, S. Zhou, P. Cappellaro, and L. Jiang, Ancilla-free quantum error correction codes for quantum metrology, Phys. Rev. Lett. 122, 040502 (2019).

[39] T. Kapourniotis and A. Datta, Fault-tolerant quantum metrology, Phys. Rev. A 100, 022335 (2019).

[40] K. C. Tan, S. Omkar, and H. Jeong, Quantum-error-correction-assisted quantum metrology without entanglement, Phys. Rev. A 100, 022312 (2019).

[41] S. Zhou and L. Jiang, The theory of entanglement-assisted metrology for quantum channels, arXiv:2003.10559 (2020a).

[42] Y. Chen, H. Chen, J. Liu, Z. Miao, and H. Yuan, Fluctuation-enhanced quantum metrology, arXiv:2003.13010 (2020).

[43] T. Baumgratz and A. Datta, Quantum enhanced estimation of a multidimensional field, Phys. Rev. Lett. 116, 030801 (2016).

[44] M. Tsang, R. Nair, and X.-M. Lu, Quantum theory of superresolution for two incoherent optical point sources, Phys. Rev. X 6, 031033 (2016).

[45] P. C. Humphreys, M. Barbieri, A. Datta, and I. A. Walmsley, Quantum enhanced multiple phase estimation, Phys. Rev. Lett. 111, 070403 (2013).

[46] M. Gessner, L. Pezzè, and A. Smerzi, Sensitivity bounds for multiparameter quantum metrology, Phys. Rev. Lett. 121, 130503 (2018).

[47] M. Tsang, H. M. Wiseman, and C. M. Caves, Fundamental quantum limit to waveform estimation, Phys. Rev. Lett. 106, 090401 (2011).

[48] D. W. Berry, M. J. W. Hall, and H. M. Wiseman, Stochastic heisenberg limit: Optimal estimation of a fluctuating phase, Phys. Rev. Lett. 111, 113601 (2013).

[49] K. Matsumoto, A new approach to the cramér-rao-type bound of the pure-state model, J. Phys. A.: Math. Theor. 35, 3111 (2002).

[50] M. G. Genoni, M. G. A. Paris, G. Adesso, H. Nha, P. L. Knight, and M. S. Kim, Optimal estimation of joint parameters in phase space, Phys. Rev. A 87, 012107 (2013).

[51] S. Ragy, M. Jarzyna, and R. Demkowicz-Dobrzański, Compatibility in multiparameter quantum metrology, Phys. Rev. A 94, 052108 (2016).

[52] H. Yuan, Sequential feedback scheme outperforms the parallel scheme for hamiltonian parameter estimation, Phys. Rev. Lett. 117, 160801 (2016).

[53] N. Kura and M. Ueda, Finite-error metrological bounds on multiparameter hamiltonian estimation, Phys. Rev. A 97, 012101 (2018).

[54] J. Liu and H. Yuan, Control-enhanced multiparameter quantum estimation, Phys. Rev. A 96, 042114 (2017).

[55] R. Nichols, P. Liuzzo-Scorpo, P. A. Knott, and G. Adesso, Multiparameter gaussian quantum metrology, Phys. Rev. A 98, 012114 (2018).

[56] W. Ge, K. Jacobs, Z. Eldredge, A. V. Gorshkov, and M. Foss-Feig, Distributed quantum metrology with linear networks and separable inputs, Phys. Rev. Lett. 121, 043604 (2018).

[57] S. L. Braunstein and C. M. Caves, Statistical distance and the geometry of quantum states, Phys. Rev. Lett. 72, 3439 (1994).

[58] C. W. Helstrom, Quantum detection and estimation theory (Academic press, 1976).

[59] A. S. Holevo, Probabilistic and Statistical Aspects of Quantum Theory (North Holland, Amsterdam, 1982).

[60] R. Demkowicz-Dobrzanski, W. Gorecki, and M. Guta, Multi-parameter estimation beyond quantum fisher information, Journal of Physics A: Mathematical and Theoretical (2020).

[61] H. Nagaoka and M. Hayashi, Asymptotic Theory of Quantum Statistical Inference (World Scientific Singapore, 2005) Chap. 8.

[62] J. Suzuki, Explicit formula for the holevo bound for two-parameter qubit-state estimation problem, J. Math. Phys. 57, 042201 (2016).

[63] M. Guţă and A. Jenčová, Local asymptotic normality in quantum statistics, Comm. Math. Phys. 276, 341 (2007).

[64] K. Yamagata, A. Fujiwara, R. D. Gill, et al., Quantum local asymptotic normality based on a new quantum likelihood ratio, Ann. Statist. 41, 2197 (2013).

[65] A. Fujiwara, Multi-parameter pure state estimation based on the right logarithmic derivative, Math. Eng. Tech. Rep 94, 94 (1994).

[66] F. Albarelli, J. F. Friel, and A. Datta, Evaluating the holevo cramér-rao bound for multiparameter quantum metrology, Phys. Rev. Lett. 123, 200503 (2019).

[67] G. Lindblad, On the generators of quantum dynamical semigroups, Comm. Math. Phys. 48, 119 (1976).

[68] V. Gorini, A. Kossakowski, and E. C. G. Sudarshan, Completely positive dynamical semigroups of n-level systems, J. Math. Phys. 17, 821 (1976).

[69] H.-P. Breuer, F. Petruccione, et al., The theory of open quantum systems (Oxford University Press on Demand, 2002).

[70] S. M. Kay, Fundamentals of statistical signal processing: estimation theory (Prentice Hall, 1993).

[71] R. Gill and S. Massar, State estimation for large ensembles, Phys. Rev. A 61, 042312 (2000).

[72] E. Knill and R. Laflamme, Theory of quantum error-correcting codes, Phys. Rev. A 55, 900 (1997).

[73] M. Grant and S. Boyd, Cvx: Matlab software for disciplined convex programming,.

[74] S. Zhou and L. Jiang, Optimal approximate quantum error correction for quantum metrology, Phys. Rev. Research 2, 013235 (2020b).

[75] W. Górecki, R. Demkowicz-Dobrzański, H. M. Wiseman, and D. W. Berry, ${pi}$-corrected heisenberg limit, Phys. Rev. Lett. 124, 030501 (2020).

[76] D. A. Lidar, I. L. Chuang, and K. B. Whaley, Decoherence-free subspaces for quantum computation, Phys. Rev. Lett. 81, 2594 (1998).

Cited by

[1] Philippe Faist, Sepehr Nezami, Victor V. Albert, Grant Salton, Fernando Pastawski, Patrick Hayden, and John Preskill, “Continuous symmetries and approximate quantum error correction”, arXiv:1902.07714.

[2] Francesco Albarelli, Jamie F. Friel, and Animesh Datta, “Evaluating the Holevo Cramér-Rao Bound for Multiparameter Quantum Metrology”, Physical Review Letters 123 20, 200503 (2019).

[3] Francesco Albarelli, Mankei Tsang, and Animesh Datta, “Upper bounds on the Holevo Cramér-Rao bound for multiparameter quantum parametric and semiparametric estimation”, arXiv:1911.11036.

[4] F. Albarelli, M. Barbieri, M. G. Genoni, and I. Gianani, “A perspective on multiparameter quantum metrology: From theoretical tools to applications in quantum imaging”, Physics Letters A 384, 126311 (2020).

[5] Yingkai Ouyang, Nathan Shettell, and Damian Markham, “Robust quantum metrology with explicit symmetric states”, arXiv:1908.02378.

[6] Emanuele Polino, Mauro Valeri, Nicolò Spagnolo, and Fabio Sciarrino, “Photonic Quantum Metrology”, arXiv:2003.05821.

[7] Sisi Zhou and Liang Jiang, “Optimal approximate quantum error correction for quantum metrology”, Physical Review Research 2 1, 013235 (2020).

[8] Rafal Demkowicz-Dobrzanski, Wojciech Gorecki, and Madalin Guta, “Multi-parameter estimation beyond Quantum Fisher Information”, arXiv:2001.11742.

[9] Sisi Zhou and Liang Jiang, “The theory of entanglement-assisted metrology for quantum channels”, arXiv:2003.10559.

[10] Aleksander Kubica and Rafal Demkowicz-Dobrzanski, “Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem”, arXiv:2004.11893.

[11] Alexander Predko, Francesco Albarelli, and Alessio Serafini, “Time-local optimal control for parameter estimation in the Gaussian regime”, Physics Letters A 384, 126268 (2020).

[12] Le Bin Ho, Hideaki Hakoshima, Yuichiro Matsuzaki, Masayuki Matsuzaki, and Yasushi Kondo, “Multiparameter quantum estimation under dephasing noise”, arXiv:2004.00720.

The above citations are from SAO/NASA ADS (last updated successfully 2020-07-02 13:02:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2020-07-02 13:02:50: Could not fetch cited-by data for 10.22331/q-2020-07-02-288 from Crossref. This is normal if the DOI was registered recently.


Continue Reading


Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm




Jessica Lemieux1, Bettina Heim2, David Poulin1,3, Krysta Svore2, and Matthias Troyer2

1Département de Physique & Institut Quantique, Université de Sherbrooke, Québec, Canada
2Quantum Architecture and Computation Group, Microsoft Research, Redmond, WA 98052, USA
3Canadian Institute for Advanced Research, Toronto, Ontario, Canada M5G 1Z8

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We present a detailed circuit implementation of Szegedy’s quantization of the Metropolis-Hastings walk. This quantum walk is usually defined with respect to an oracle. We find that a direct implementation of this oracle requires costly arithmetic operations. We thus reformulate the quantum walk, circumventing its implementation altogether by closely following the classical Metropolis-Hastings walk. We also present heuristic quantum algorithms that use the quantum walk in the context of discrete optimization problems and numerically study their performances. Our numerical results indicate polynomial quantum speedups in heuristic settings.

► BibTeX data

► References

[1] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the thirty-fifth ACM symposium on Theory of computing – STOC ’03, page 20, New York, New York, USA, 2003. ACM Press. ISBN 1581136749. 10.1145/​780542.780546.

[2] Andris Ambainis. Quantum walk algorithm for element distinctness. In Proceedings – Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 22–31, 2004. 10.1109/​focs.2004.54.

[3] Francisco Barahona. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical and General, 15: 3241–3253, 1982. 10.1088/​0305-4470/​15/​10/​028.

[4] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. Divincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical Review A, 52 (5): 3457–3467, nov 1995. ISSN 10502947. 10.1103/​PhysRevA.52.3457.

[5] Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of probabilistic quantum circuits with fallback. Physical Review A – Atomic, Molecular, and Optical Physics, 91 (5): 052317, may 2015. ISSN 10941622. 10.1103/​PhysRevA.91.052317.

[6] S. Boixo, E. Knill, and R. D. Somma. Fast quantum algorithms for traversing paths of eigenstates. may 2010. URL https:/​/​​abs/​1005.3034.

[7] Sergio Boixo, Emanuel Knill, and Rolando Somma. Eigenpath traversal by phase randomization. Quantum Information and Computation, 9 (9&10): 0833, 2009. URL http:/​/​​abs/​0903.1652.

[8] N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik, and Yoshihisa Yamamoto. Faster quantum chemistry simulation on fault-tolerant quantum computers. New Journal of Physics, 14 (11): 115023, nov 2012. ISSN 1367-2630. 10.1088/​1367-2630/​14/​11/​115023.

[9] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum Computation by Adiabatic Evolution. jan 2000. URL http:/​/​​abs/​quant-ph/​0001106.

[10] Roy J. Glauber. Time-dependent statistics of the Ising model. Journal of Mathematical Physics, 4 (2): 294–307, feb 1963. ISSN 00222488. 10.1063/​1.1703954.

[11] Jeongwan Haah. Product Decomposition of Periodic Functions in Quantum Signal Processing. jun 2018. 10.22331/​q-2019-10-07-190.

[12] W K Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57 (1): 97–109, apr 1970. ISSN 0006-3444. 10.1093/​biomet/​57.1.97.

[13] Janus Collaboration, F. Belletti, M. Cotallo, A. Cruz, L. A. Fernández, A. Gordillo, M. Guidetti, A. Maiorano, F. Mantovani, E. Marinari, V. Martín-Mayor, A. Muñoz-Sudupe, D. Navarro, G. Parisi, S. Pérez-Gaviro, M. Rossi, J. J. Ruiz-Lorenzo, S. F. Schifano, D. Sciretti, A. Tarancón, R. Tripiccione, and J. L. Velasco. JANUS: an FPGA-based System for High Performance Scientific Computing. Computing in Science & Engineering, 11 (1): 48–58, 2009. 10.1109/​MCSE.2009.11.

[14] Janus Collaboration, M. Baity-Jesi, R. A. Banos, A. Cruz, L. A. Fernandez, J. M. Gil-Narvion, A. Gordillo-Guerrero, M. Guidetti, D. Iniguez, A. Maiorano, F. Mantovani, E. Marinari, V. Martin-Mayor, J. Monforte-Garcia, A. Munoz Sudupe, D. Navarro, G. Parisi, M. Pivanti, S. Perez-Gaviro, F. Ricci-Tersenghi, J. J. Ruiz-Lorenzo, S. F. Schifano, B. Seoane, A. Tarancon, P. Tellez, R. Tripiccione, and D. Yllanes. Reconfigurable computing for Monte Carlo simulations: results and prospects of the Janus project. The European Physical Journal Special Topics, 210 (33), 2012. 10.1140/​epjst/​e2012-01636-9.

[15] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220 (4598): 671–680, 1983. ISSN 00368075. 10.1126/​science.220.4598.671.

[16] A. Yu. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. nov 1995. URL http:/​/​​abs/​quant-ph/​9511026.

[17] Jessica Lemieux, Guillaume Duclos-Cianci, David Sénéchal, and David Poulin. Resource estimate for quantum many-body ground state preparation on a quantum computer. 2020. URL https:/​/​​abs/​2006.04650.

[18] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. oct 2016. 10.22331/​q-2019-07-12-163.

[19] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian Simulation by Quantum Signal Processing. Physical Review Letters, 118 (1): 010501, jan 2017. ISSN 10797114. 10.1103/​PhysRevLett.118.010501.

[20] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. Methodology of resonant equiangular composite quantum gates. Physical Review X, 6 (4): 041067, dec 2016. ISSN 21603308. 10.1103/​PhysRevX.6.041067.

[21] F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. SIAM Journal on Computing, 40: 142–164. 10.1137/​090745854.

[22] Chris Marriott and John Watrous. Quantum Arthur-Merlin games. In Computational Complexity, volume 14, pages 122–152. Springer, jun 2005. 10.1007/​s00037-005-0194-x.

[23] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21 (6): 1087–1092, jun 1953. ISSN 00219606. 10.1063/​1.1699114.

[24] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345 (6195): 420–424, jul 2014. ISSN 10959203. 10.1126/​science.1252319.

[25] Neil J Ross and Peter Selinger. Optimal ancilla-free Clifford+T approximation of Z-rotations. Quantum Information and Computation, 16 (11&12): 0901, 2016. URL http:/​/​​abs/​1403.2975.

[26] Terry Rudolph and Lov Grover. A 2 rebit gate universal for quantum computing. oct 2002. URL https:/​/​​abs/​quant-ph/​0210187.

[27] R. D. Somma, S. Boixo, H. Barnum, and E. Knill. Quantum simulations of classical annealing processes. Physical Review Letters, 101 (13): 130504, sep 2008. ISSN 00319007. 10.1103/​PhysRevLett.101.130504.

[28] Mario Szegedy. Quantum speed-up of Markov Chain based algorithms. In Proceedings – Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 32–41, 2004. 10.1109/​focs.2004.53.

[29] K. Temme, T. J. Osborne, K. G. Vollbrecht, D. Poulin, and F. Verstraete. Quantum Metropolis sampling. Nature, 471 (7336): 87–90, mar 2011. ISSN 00280836. 10.1038/​nature09770.

[30] Marija Vucelja. Lifting—A nonreversible Markov chain Monte Carlo algorithm. American Journal of Physics, 84 (12): 958–968, dec 2016. ISSN 0002-9505. 10.1119/​1.4961596.

[31] Man-Hong Yung and Alán Aspuru-Guzik. A quantum-quantum Metropolis algorithm. Proceedings of the National Academy of Sciences of the United States of America, 109 (3): 754–9, jan 2012. ISSN 1091-6490. 10.1073/​pnas.1111758109.

Cited by

[1] Jessica Lemieux, Guillaume Duclos-Cianci, David Sénéchal, and David Poulin, “Resource estimate for quantum many-body ground state preparation on a quantum computer”, arXiv:2006.04650.

The above citations are from SAO/NASA ADS (last updated successfully 2020-06-29 12:29:48). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2020-06-29 12:29:47: Could not fetch cited-by data for 10.22331/q-2020-06-29-287 from Crossref. This is normal if the DOI was registered recently.


Continue Reading
Fintech3 hours ago

UK fintech startup pirkx launches in Australia

Publications3 hours ago

U.S. stock futures are flat as global coronavirus cases climb at record pace

Blockchain4 hours ago

Bitcoin Just Plunged Under $9,000: Here’s What Analysts Are Saying

Blockchain4 hours ago

Ethereum’s Vitalik Buterin may have made crypto-tribalism worse

Publications4 hours ago

Blowout jobs report may have missed a troubling trend linked to coronavirus

Blockchain4 hours ago

Bitcoin Stagnates, Criminals Targeted, $288K Prediction: Hodler’s Digest, June 29–July 5

Covid194 hours ago

Boris Johnson pledges £1.5bn lifeline to keep UK’s arts sector afloat

Blockchain5 hours ago

Altcoin ‘Mass Extinction’ Will Likely Precede Next Bitcoin Rally, Crypto Whale Posits

Blockchain5 hours ago

Antifa Threatened With Extremist Status: No Longer Thinks Bitcoin Is an Alt-Right Currency Antifa and BLM Will Make Bitcoin Edgy Again

CovId195 hours ago

Coronavirus: Texas mayors warn of ‘serious trouble’ as cases surge across US

Blockchain5 hours ago

3 Reasons Why Bloomberg Calling Bitcoin a ‘Resting Bull’ Is Inaccurate

Energy5 hours ago

Tesla Begins Taking Cybertruck Orders In China, Will Drive One Across America

IOT5 hours ago

Syringes Put the Squeeze On This Mini Drill Press

Blockchain5 hours ago

Will Bitcoin Hit $288,000 by December of 2021? New Poll Reveals Crypto Trader Sentiment on BTC

Ethereum/Bitcoin correlation
Blockchain5 hours ago

Textbook Pattern Predicts Ethereum Will Plunge Over 20% if $220 Is Lost

Blockchain5 hours ago

Litecoin short-term price analysis: 05 July

Blockchain5 hours ago

Bitcoin Surged 150% After This Signal Last Appeared. It’s Almost Back Again

Automotive5 hours ago

Commentary: The power of control

Blockchain5 hours ago

Ripple Price Prediction: XRP/USD Is Stuck Between $0.17 and $18, as the Downtrend Is Unrelenting

CovId195 hours ago

Coronavirus live: Spain puts part of Galicia back into lockdown; doubts over Republican National Convention

CovId196 hours ago

Trump claims victory as US nears 130,000 coronavirus deaths – live

Blockchain6 hours ago

Smart Vending Machine Maker Popcom Crowdfunds $1.3M

Gaming6 hours ago

Tencent’s new blockbuster US game studio is led by a ‘GTA’ veteran

AI6 hours ago

Is Recogni Critical To Autonomous Vehicles From Legacy Automakers?

Blockchain6 hours ago

Philippine Regulator Warns Against Crypto Schemes

Blockchain6 hours ago

Cardano long-term price analysis: 05 July

Blockchain6 hours ago

Voice Social Network Officially Launches On EOS Blockchain

Blockchain6 hours ago

Block Fi Has Seen Its Income Double in Two Months

Blockchain6 hours ago

Cardano (ADA) May Soon Crater by 25% as Massive Resistance Looms

Automotive6 hours ago

Junkyard Gem: 1973 Chevrolet Vega with V8 Swap

Big Data6 hours ago

Statistics for Data Science: What is Skewness and Why is it Important?

Blockchain7 hours ago

Brock Pierce Announces He Will Run In The 2020 US Presidential Elections

Blockchain7 hours ago

VeChain Blockchain For Food Tracking Will Trace $300B By 2027: Report

Blockchain7 hours ago

Ethereum Is Lacking Momentum Even With New Signs For Rally

Cannabis7 hours ago

Authorities Incinerate Nearly 15 Tons of Cannabis in Morocco’s Dakhla

Automotive7 hours ago

Trump signs PPP extension, program lives until August 8

CovId197 hours ago

Iran admits incident at Natanz nuclear site caused major damage

Blockchain7 hours ago

Binance Supports New Ontology 2.0 Upgrades

Cannabis7 hours ago

Best CBD Oil Company in Dublin & Ireland

Crowdfunding7 hours ago

As Ethereum 2.0 Mainnet Gets Ready to Launch, Co-founder Vitalik Buterin Admits Developers Overlooked Sharding, Proof of Stake Design Issues